sacgajcvs

Untitled

Oct 14th, 2020
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.05 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define LL long long int
  3. #define M 1000000007
  4. #define reset(a) memset(a,0,sizeof(a))
  5. #define rep(i,j,k) for(i=j;i<=k;++i)
  6. #define per(i,j,k) for(i=j;i>=k;--i)
  7. #define print(a,start,end) for(i=start;i<=end;++i) cout<<a[i];
  8. #define endl "\n"
  9. #define eps 0.00000001
  10. #define check(a , b , c) assert(a >= b && a <= c)
  11. LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
  12. LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
  13. LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
  14. using namespace std;
  15. int u[200001];
  16. int v[200001];
  17. int w[200001];
  18. vector<int> graph[200001];
  19. bool visit[200001];
  20. int sz = 0;
  21. int eg = 0;
  22. int deg[200001];
  23. vector<pair<int,int> > watered;
  24. vector<pair<int,int> > dry;
  25. void dfs(int node)
  26. {
  27. sz++;
  28. visit[node] = 1;
  29. eg += deg[node];
  30. for(int i: graph[node])
  31. {
  32. if(visit[i] == 0)
  33. {
  34. visit[i] = 1;
  35. dfs(i);
  36. }
  37. }
  38. }
  39. int main()
  40. {
  41. ios_base::sync_with_stdio(0);
  42. int n , m , k;
  43. cin >> n >> m >> k;
  44. for(int i = 0; i < m; i++)
  45. {
  46. cin >> u[i] >> v[i];
  47. graph[u[i]].push_back(v[i]);
  48. graph[v[i]].push_back(u[i]);
  49. ++deg[u[i]];
  50. ++deg[v[i]];
  51. }
  52. for(int i = 0; i < k; i++)
  53. cin >> w[i];
  54. LL ans1 = 0 , ans2 = 0;
  55. LL maxsz = 0;
  56. for(int i = 0; i < k; i++)
  57. {
  58. sz = 0;
  59. eg = 0;
  60. if(visit[w[i]] == 1)
  61. continue;
  62. dfs(w[i]);
  63. maxsz = max(maxsz , (LL)sz);
  64. eg /= 2;
  65. watered.push_back(make_pair(sz , eg));
  66. ans1 += (sz * (sz - 1)) / 2 - eg;
  67. }
  68. for(int i = 1; i <= n; i++)
  69. {
  70. if(visit[i] == 0)
  71. {
  72. sz = 0;
  73. eg = 0;
  74. dfs(i);
  75. eg /= 2;
  76. dry.push_back(make_pair(sz , eg));
  77. ans1 += (sz * (sz - 1)) / 2 - eg;
  78. }
  79. }
  80. sort(watered.begin() , watered.end());
  81.  
  82. LL pre = 0 , cur = 0;
  83. for(int i = 0; i < dry.size(); i++)
  84. {
  85. ans2 = ans2 + pre * dry[i].first;
  86. ans1 += pre * dry[i].first;
  87. pre += dry[i].first;
  88. }
  89.  
  90. ans2 += pre * maxsz;
  91. ans1 += pre * maxsz;
  92. cout << ans1 << " " << ans2;
  93.  
  94. }
  95.  
Advertisement
Add Comment
Please, Sign In to add comment