#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
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 time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
9728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
