#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int r[N];
using ll = long long;
ll ans=0;
bool czy[N];
int ile=0;
set<int> S[N], co[N];
int find(int i){
if(i==r[i])return i;
return r[i]=find(r[i]);
}
void Union(int a,int b){
if(a==b)return;
if(S[a].size()+co[a].size()>S[b].size()+co[b].size())swap(a, b);
ans-=S[a].size()*1ll*co[a].size();
ans-=S[b].size()*1ll*co[b].size();
for(int i:S[a])if(co[b].find(i)!=co[b].end() && !czy[i])czy[i]=1, ile++;
for(int i:co[a])if(S[b].find(i)!=S[b].end() && !czy[i])czy[i]=1, ile++;
for(int i:S[a])S[b].insert(i);
for(int i:co[a])co[b].insert(i);
ans+=S[b].size()*1ll*co[b].size();
r[a]=b;
}
int main(){
int n, q;
cin>>n>>q;
for(int i=1; i<=n; i++)r[i]=i, co[i].insert(i);
while(q--){
int u, v;
cin>>u>>v;
int vv=v;
v=find(v);
if(S[v].find(u)==S[v].end()){
//cout<<"a";
S[v].insert(u);
ans+=co[v].size();
if(v==find(u) && !czy[u])czy[u]=1, ile++;
}
if(S[find(u)].find(vv)!=S[find(u)].end()){
//cout<<"b";
Union(find(u), v);
}
cout<<ans-ile<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
