fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, M, K;
  5. int B[100001], G[100001];
  6. vector<int> adjList[100001];
  7. bool visited[100001];
  8. vector<int> gossip;
  9.  
  10. void visit(int now) {
  11. visited[now] = true;
  12. gossip.push_back(B[now]);
  13. for(int i = 0; i < adjList[now].size(); i++)
  14. if(!visited[adjList[now][i]])
  15. visit(adjList[now][i]);
  16. return;
  17. }
  18.  
  19. int main() {
  20. cin >> N >> M >> K;
  21. for(int i = 0; i < N; i++)
  22. adjList[i].clear();
  23. for(int i = 0; i < N; i++)
  24. cin >> B[i];
  25. for(int i = 0; i < M; i++)
  26. cin >> G[i];
  27. sort(G, G+M);
  28. for(int i = 0; i < K; i++) {
  29. int a, b;
  30. cin >> a >> b;
  31. a--; b--;
  32. adjList[a].push_back(b);
  33. adjList[b].push_back(a);
  34. }
  35. memset(visited, false, sizeof(visited));
  36. int ans = 0;
  37. for(int i = 0; i < N; i++)
  38. if(!visited[i]) {
  39. gossip.clear();
  40. visit(i);
  41. sort(gossip.begin(), gossip.end());
  42. int candy, sum1 = 0, sum2 = 0;
  43. if(gossip.size()%2 == 1) // odd
  44. candy = lower_bound(G, G+M, gossip[gossip.size()/2])-G;
  45. else // even
  46. candy = lower_bound(G, G+M, (gossip[gossip.size()/2-1]+gossip[gossip.size()/2])/2)-G;
  47. for(int i = 0; i < gossip.size(); i++) {
  48. if(candy < M)
  49. sum1 += abs(G[candy]-gossip[i]);
  50. if(candy > 0)
  51. sum2 += abs(G[candy-1]-gossip[i]);
  52. }
  53. if(candy == 0)
  54. sum2 = 1e9;
  55. if(candy == M)
  56. sum1 = 1e9;
  57. ans += min(sum1, sum2);
  58. /*
  59. for(int i = 0; i < gossip.size(); i++)
  60. cout << gossip[i] << " ";
  61. cout << candy << " " << sum1 << " " << sum2 << endl;
  62. /**/
  63. }
  64. cout << ans << endl;
  65. return 0;
  66. }
Success #stdin #stdout 0.01s 5868KB
stdin
8 4 6
10 20 30 400 50 60 70 80
30 40 50 60
1 8
2 7
3 5
3 6
5 6
6 8
stdout
490