# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
211993 | 2020-03-21T22:19:27 Z | sealnot123 | Making Friends on Joitter is Fun (JOI20_joitter2) | C++14 | 10 ms | 9728 KB |
#include<bits/stdc++.h> #define x first #define y second #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define SZ(a) (int)(a).size() using namespace std; typedef pair<int,int> PII; typedef long long LL; typedef double DD; typedef long double LD; typedef pair<LL,LL> PLL; typedef pair<DD,DD> PDD; typedef vector<int> VI; typedef vector<LL> VL; const int N=100007; LL ans = 0; multiset<int> I[N], O[N]; multiset<int>::iterator it, it2; int p[N], s[N]; int fin(int a){ if(a == p[a]) return a; return p[a] = fin(p[a]); } set<int> wait; LL val(int a){ return (LL)s[a]*(s[a]-1) + (LL)SZ(I[a])*s[a]; } void merge(int a, int b){ /*printf("(%d,%d)\n",a,b);*/ ans -= val(a)+val(b); /*printf("asdfdas %d\n",ans);*/ I[a].erase(b); O[a].erase(b); I[b].erase(a); O[b].erase(a); if(SZ(I[a])+SZ(O[a]) < SZ(I[b])+SZ(O[b])) swap(a,b); int i,j; for(it = I[b].begin(); it != I[b].end(); it++){ it2 = O[a].find(*it); if(it2 != O[a].end()) wait.insert(*it); O[*it].insert(a); I[a].insert(*it); } for(it = I[b].begin(); it != I[b].end(); it++) O[*it].erase(b); for(it = O[b].begin(); it != O[b].end(); it++){ it2 = I[a].find(*it); if(it2 != I[a].end()) wait.insert(*it); I[*it].insert(a); O[a].insert(*it); } for(it = O[b].begin(); it != O[b].end(); it++) I[*it].erase(b); I[b].clear(); O[b].clear(); /*printf("result %d(%d) :\n",a,s[a]+s[b]); printf("in : "); for(int e : I[a]) printf("%d ",e); printf("\nout : "); for(int e : O[a]) printf("%d ",e); printf("\n");*/ p[b] = a; s[a] += s[b]; ans += val(a); if(wait.empty()) return; int x = *wait.begin(); wait.erase(wait.begin()); merge(a, x); } int main(){ int i,j,k,l,a,b,c,d; int n, m; scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ s[i] = 1; p[i] = i; } while(m--){ scanf("%d%d",&a,&b); a = fin(a); b = fin(b); if(a != b){ it = O[a].find(b); if(it == O[a].end()){ it = I[a].find(b); if(it != I[a].end()){ /*printf("must merge\n");*/ merge(a, b); }else{ O[a].insert(b); I[b].insert(a); ans += s[b]; } } } /*printf("XXXXXXXXXXXXXXXXXXXx");*/ printf("%lld\n",ans); } return 0; } /* 4 6 1 2 2 3 3 2 1 3 3 4 4 3 6 10 1 2 2 3 3 4 4 5 5 6 6 5 5 4 4 3 3 2 2 1 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 10 ms | 9728 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 10 ms | 9728 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 10 ms | 9728 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |