Submission #278573

#TimeUsernameProblemLanguageResultExecution timeMemory
278573MKopchevMaking Friends on Joitter is Fun (JOI20_joitter2)C++14
0 / 100
7 ms9728 KiB
#include<bits/stdc++.h> using namespace std; const int nmax=1e5+42; int n,m; int parent[nmax],SZ[nmax]; int root(int node) { if(node==parent[node])return node; parent[node]=root(parent[node]); return parent[node]; } set< pair<int/*from*/,int/*to component*/> > all[nmax]; set< int > component[nmax]; set< pair<int/*from*/,int/*to*/> > edges_comp; long long output=0; int in[nmax]; long long score(int node) { node=root(node); return 1LL*SZ[node]*(SZ[node]-1)/2*2+1LL*in[node]*SZ[node]; } void add(int u,int v) { /* cout<<"\n\n\n"<<endl; cout<<"add "<<u<<" "<<v<<" "<<output<<endl; cout<<"edges_comp"<<endl; for(auto k:edges_comp)cout<<k.first<<" "<<k.second<<endl; for(int i=1;i<=n;i++) { cout<<i<<" -> "<<in[i]<<" "<<root(i)<<" "<<SZ[root(i)]<<endl; cout<<"all: "<<endl; for(auto j:all[i])cout<<j.first<<" "<<j.second<<endl; cout<<"component: ";for(auto k:component[i])cout<<k<<" ";cout<<endl; cout<<"---"<<endl; } */ int u_root=root(u); int v_root=root(v); if(u_root==v_root)return; if(all[u_root].count({u,v_root}))return; if(edges_comp.count({v_root,u_root})==0)//do not merge { output+=SZ[v_root]; in[v_root]++; all[u_root].insert({u,v_root}); all[v_root].insert({u,v_root}); edges_comp.insert({u_root,v_root}); return; } /* if(SZ[u_root]<SZ[v_root]) { swap(u_root,v_root); swap(u,v); } */ edges_comp.erase({u_root,v_root}); edges_comp.erase({v_root,u_root}); //cout<<u_root<<" "<<u<<" "<<v_root<<" "<<v<<endl; //merge output=output-score(u_root)-score(v_root); //cout<<"after sub "<<output<<endl; set< pair<int/*from*/,int/*to component*/> > mem_all=all[v_root]; for(auto p:mem_all) { int where=-1; pair<int,int> k=p; //cout<<"moving "<<k.first<<" "<<k.second<<endl; if(k.second==v_root&&component[u_root].count(k.first)) { all[u_root].erase({k.first,v_root}); all[v_root].erase({k.first,v_root}); in[v_root]--; where=1; } else if(k.second==v_root) { all[root(k.first)].erase(k); k.second=u_root; if(all[u_root].count(k)==0)in[u_root]++; all[u_root].insert(k); all[root(k.first)].insert(k); edges_comp.insert({root(k.first),u_root}); edges_comp.erase({root(k.first),v_root}); where=2; } else if(component[u_root].count(k.second)==0) { //if(all[u_root].count({u_root,root(k.second)})==0)output+=SZ[u_root];in[root(k.second)]++; all[u_root].insert({k.first,root(k.second)}); all[root(k.second)].insert({k.first,root(k.second)}); edges_comp.insert({u_root,root(k.second)}); /* cout<<"Wrong "<<endl; system("pause"); */ where=3; } else { in[u_root]--; all[u_root].erase({k.first,u_root}); all[v_root].erase({k.first,u_root}); where=4; } //cout<<"where= "<<where<<" "<<in[u_root]<<endl; } all[v_root]={}; in[v_root]=0; SZ[u_root]+=SZ[v_root]; parent[v_root]=u_root; output+=score(u_root); //cout<<"after add "<<output<<endl; for(auto k:component[v_root]) component[u_root].insert(k); component[v_root]={}; for(auto k:mem_all) if(k.second==v_root)add(k.first,u_root); } int main() { scanf("%i%i",&n,&m); for(int i=1;i<=n;i++)parent[i]=i,SZ[i]=1,component[i]={i}; for(int i=1;i<=m;i++) { int u,v; scanf("%i%i",&u,&v); add(u,v); printf("%lld\n",output); } return 0; }

Compilation message (stderr)

joitter2.cpp: In function 'void add(int, int)':
joitter2.cpp:90:13: warning: variable 'where' set but not used [-Wunused-but-set-variable]
   90 |         int where=-1;
      |             ^~~~~
joitter2.cpp: In function 'int main()':
joitter2.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  169 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
joitter2.cpp:177:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  177 |         scanf("%i%i",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...