#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int N,M;
ll rod[maxn],vel[maxn];
ll res;
set<int> cukomp[maxn],kompuc[maxn],compout[maxn],compin[maxn];
vector<int> koji[maxn];
int getpar(int x){
if(rod[x]==x)
return x;
rod[x]=getpar(rod[x]);
return rod[x];
}
void pretvori(int a,int b){
for(auto it=kompuc[a].begin();it!=kompuc[a].end();it++){
cukomp[*it].erase(a);
if(getpar(*it)!=b)
cukomp[*it].insert(b);
}
// cout<<"A"<<endl;
for(auto it=compout[a].begin();it!=compout[a].end();it++){
compin[*it].erase(a);
compin[*it].insert(b);
}
//cout<<"B"<<endl;
for(auto it=compin[a].begin();it!=compin[a].end();it++){
compout[*it].erase(a);
compout[*it].insert(b);
}
// cout<<"C"<<endl;
}
void spoj(int a,int b){ /// a i b su indeksi komponenti
if(vel[b]>vel[a])
swap(a,b);
res-=vel[a]*kompuc[a].size();
res-=vel[a]*(vel[a]-1);
res-=vel[b]*kompuc[b].size();
res-=vel[b]*(vel[b]-1);
//cout<<res<<endl;
compin[a].erase(b);
compout[a].erase(b);
compin[b].erase(a);
compout[b].erase(a);
//cout<<"OVDE"<<endl;
vel[a]+=vel[b];
rod[b]=a;
pretvori(b,a);
// cout<<"OKK"<<endl;
for(int i=0;i<koji[b].size();i++){
kompuc[a].erase(koji[b][i]);
koji[a].push_back(koji[b][i]);
}
for(auto it=compin[b].begin();it!=compin[b].end();it++)
compin[a].insert(*it);
for(auto it=compout[b].begin();it!=compout[b].end();it++)
compout[a].insert(*it);
for(auto it=kompuc[b].begin();it!=kompuc[b].end();it++)
if(getpar(*it)!=a)
kompuc[a].insert(*it);
res+=vel[a]*(vel[a]-1);
res+=vel[a]*kompuc[a].size();
// cout<<vel[a]<<" "<<kompuc[a].size()<<endl;
return;
}
void odradi(int a,int b){
int ca=getpar(a);
int cb=getpar(b);
if(ca==cb)
return;
if(cukomp[a].find(cb)!=cukomp[a].end())
return;
if(compout[cb].find(ca)!=compout[cb].end()){
spoj(ca,cb);
return;
}
res+=vel[cb];
cukomp[a].insert(cb);
kompuc[cb].insert(a);
compin[cb].insert(ca);
compout[ca].insert(cb);
return;
}
int main(){
cin>>N>>M;
for(int i=1;i<=N;i++){
vel[i]=1;
rod[i]=i;
koji[i].push_back(i);
}
res=0;
int a,b;
while(M--){
cin>>a>>b;
odradi(a,b);
cout<<res<<"\n";
}
return 0;
}
Compilation message
joitter2.cpp: In function 'void spoj(int, int)':
joitter2.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0;i<koji[b].size();i++){
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
11 ms |
21352 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
21332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
11 ms |
21352 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
21332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
21452 KB |
Output is correct |
| 2 |
Correct |
11 ms |
21352 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
21332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
