#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
typedef long long ll;
ll ans = 0;
int n,m;
struct DSU{
int p,sz,nr;
set <pair<int,int>> boys;
vector <int> comp;
}dsu[N];
int leader(int x){
if(x == dsu[x].p)return x;
return dsu[x].p = leader(dsu[x].p);
}
void connect(int x,int y){
//cout<<"MERGE:"<<x<<' '<<y<<'\n';
x = leader(x);
y = leader(y);
if(x == y)return;
if(dsu[x].sz > dsu[y].sz)swap(x,y);
for(auto i:dsu[x].comp){
dsu[y].comp.push_back(i);
}
if(dsu[x].boys > dsu[y].boys)swap(x,y);
set<pair<int,int>>::iterator id = dsu[y].boys.begin();
while(id != dsu[y].boys.end()){
auto i = *id;
int u = leader(i.first);
int w = leader(i.second);
if((u == x || u == y) && (w == x || w == y)){
assert(u != w);
if(w == y){
ans-=dsu[y].sz;
dsu[y].nr--;
}else{
ans-=dsu[x].sz;
dsu[x].nr--;
}
id = next(id);
dsu[y].boys.erase(i);
}else{
id++;
}
}
for(auto i:dsu[x].boys){
int u = leader(i.first);
int w = leader(i.second);
if((u == x || u == y) && (w == x || w == y)){
assert(u != w);
if(w == y){
ans-=dsu[y].sz;
dsu[y].nr--;
}else{
ans-=dsu[x].sz;
dsu[x].nr--;
}
}else{
dsu[y].boys.insert(i);
}
}
dsu[x].boys.clear();
ans+=2ll*dsu[x].sz*dsu[y].sz;
ans+=1ll*dsu[x].nr*dsu[y].sz;
ans+=1ll*dsu[x].sz*dsu[y].nr;
dsu[x].p = y;
dsu[x].nr+=dsu[y].nr;
dsu[y].sz+=dsu[x].sz;
}
bool checkedge(int x,int y){
int compx = leader(x);
int compy = leader(y);
if(compx == compy)return 1;
set<pair<int,int>>::iterator it = dsu[compx].boys.lower_bound({x,-1});
while(it != dsu[compx].boys.end() && it->first == x){
if(leader(it->second) == compy)return 1;
it++;
}
return 0;
}
void addedge(int x,int y){
int compx = leader(x);
int compy = leader(y);
if(checkedge(x,y))return;
if(checkedge(y,x)){
connect(x,y);
}else{
dsu[compx].boys.insert({x,y});
dsu[compy].nr++;
ans+=dsu[compy].sz;
}
}
void dbg(){
for(int i = 0;i < n;i++){
cout<<"dsuinvestigate:"<<i<<'\n';
cout<<dsu[i].p<<' '<<dsu[i].sz<<' '<<dsu[i].nr<<'\n';
for(auto j:dsu[i].boys)cout<<j.first<<' '<<j.second<<'\n';cout<<'\n';
for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
}
}
int main(){
cin>>n>>m;
for(int i = 0;i < n;i++){
dsu[i] = {i,1};
dsu[i].comp.push_back(i);
}
for(int i = 0;i < m;i++){
int u,w;
cin>>u>>w;
u--;w--;
addedge(u,w);
//dbg();
cout<<ans<<'\n';
}
return 0;
}
Compilation message
joitter2.cpp: In function 'void dbg()':
joitter2.cpp:97:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
97 | for(auto j:dsu[i].boys)cout<<j.first<<' '<<j.second<<'\n';cout<<'\n';
| ^~~
joitter2.cpp:97:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
97 | for(auto j:dsu[i].boys)cout<<j.first<<' '<<j.second<<'\n';cout<<'\n';
| ^~~~
joitter2.cpp:98:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
98 | for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
| ^~~
joitter2.cpp:98:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
98 | for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
17500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
17500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
17500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
