Submission #377181

#TimeUsernameProblemLanguageResultExecution timeMemory
377181nafis_shifatMaking Friends on Joitter is Fun (JOI20_joitter2)C++14
17 / 100
1635 ms125812 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define f first #define s second using namespace std; const int mxn=1e5+5; const int inf=1e9; int parent[mxn]; int sz[mxn]; set<int> adj[mxn]; set<int> in[mxn]; vector<int> nodes[mxn]; int sz2[mxn][2]; set<int> eds[mxn][2]; set<int> reps[mxn]; set<int> ireps[mxn]; ll ans = 0; int findrep(int u) { return parent[u] == u ? u : parent[u] = findrep(parent[u]); } void unite(int u,int v) { int U = findrep(u); int V = findrep(v); if(U == V) return; if(adj[V].count(U)) { ans += 2 * sz[U] * sz[V]; if(sz[U] + sz2[U][0] + sz2[U][1] > sz[V] + sz2[V][0] + sz2[V][1]) swap(U,V); vector<int> nod1,nod2; for(int i : nodes[U]) { auto it1 = eds[i][0].begin(); while(it1 != eds[i][0].end()) { int x = *it1; int X = findrep(x); if(X == V) { ans -= sz[V]; in[V].erase(U); adj[U].erase(V); eds[x][1].erase(i); sz2[X][1]--; it1 = eds[i][0].erase(it1); sz2[U][0]--; } else if(in[V].count(X)) { nod1.push_back(X); in[X].erase(U); eds[x][1].erase(i); sz2[X][1]--; ans -= sz[X]; it1 = eds[i][0].erase(it1); sz2[U][0]--; } else it1++; } auto it2 = eds[i][1].begin(); while(it2 != eds[i][1].end()) { int x = *it2; int X = findrep(x); if(X == V) { ans -= sz[U]; adj[V].erase(U); in[U].erase(V); eds[x][0].erase(i); sz2[X][0]--; it2 = eds[i][1].erase(it2); sz2[U][1]--; } else if(adj[V].count(X)) { nod2.push_back(X); adj[X].erase(U); eds[x][0].erase(i); sz2[X][0]--; ans -= sz[U]; it2 = eds[i][1].erase(it2); sz2[U][1]--; } else if(ireps[V].count(x)) { sz2[U][1]--; reps[x].erase(U); eds[x][0].erase(i); sz2[X][0]--; it2 = eds[i][1].erase(it2); ans -= sz[U]; } else it2++; } } while(!ireps[U].empty()) { auto it = ireps[U].begin(); ireps[V].insert(*it); reps[*it].erase(U); reps[*it].insert(V); ireps[U].erase(it); } ans += sz2[U][1] * sz[V]; ans += sz2[V][1] * sz[U]; parent[U] = V; sz[V] += sz[U]; sz2[V][0] += sz2[U][0]; sz2[V][1] += sz2[U][1]; while(!nodes[U].empty()) { int x = nodes[U].back(); nodes[U].pop_back(); nodes[V].push_back(x); } while(!adj[U].empty()) { int x = *adj[U].begin(); in[x].erase(U); adj[U].erase(x); adj[V].insert(x); in[x].insert(V); } while(!in[U].empty()) { int x = *in[U].begin(); in[U].erase(x); adj[x].erase(U); in[V].insert(x); adj[x].insert(V); } for(int x : nod1) { unite(V,x); } for(int x : nod2) { unite(x,V); } } else { if(reps[u].count(V)) return; ans += sz[V]; eds[u][0].insert(v); eds[v][1].insert(u); adj[U].insert(V); in[V].insert(U); reps[u].insert(V); ireps[V].insert(u); sz2[U][0]++; sz2[V][1]++; } } int main() { int n,m; cin >> n >> m; for(int i = 1; i <= n; i++) { parent[i] = i; sz[i] = 1; sz2[i][0] = sz2[i][1] = 0; nodes[i].push_back(i); } for(int i = 1; i <= m; i++) { int u,v; scanf("%d%d",&u,&v); unite(u,v); cout<<ans<<endl; } }

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:196:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  196 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...