//#define __GLIBCXX_DEBUG
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
struct no{
int bo,sz;
map<int,int> tb,fb;
set<int> tp,fp;
vector<int> ch;
};
vector<no> v;
long long ans=0;
int find(int a){
return v[a].bo==a?a:v[a].bo=find(v[a].bo);
}
void merge(int x,int y){
queue<pair<int,int> > q;
q.push({x,y});
while(!q.empty()){
auto g=q.front();
q.pop();
int a=find(g.fs),b=find(g.sc);
if(a==b){
continue;
}
if(v[a].sz>v[b].sz){
swap(a,b);
}
ans-=1ll*v[b].tp.size()*v[b].sz;
ans-=1ll*v[a].tp.size()*v[a].sz;
ans-=1ll*(v[b].sz)*(v[b].sz-1);
ans-=1ll*(v[a].sz)*(v[a].sz-1);
for(auto y:v[a].tp){
int u=find(y);
if(u==b){
continue;
}
v[b].tp.insert(y);
v[u].fb.erase(a);
v[u].fb[b]++;
}
for(auto y:v[a].fp){
int u=find(y);
if(u==b){
continue;
}
v[b].fp.insert(y);
v[u].tb.erase(a);
v[u].tb[b]++;
}
for(auto y:v[a].ch){
v[b].tp.erase(y);
v[b].fp.erase(y);
v[b].ch.push_back(y);
}
v[b].sz+=v[a].sz;
v[a].bo=b;
ans+=1ll*v[b].tp.size()*v[b].sz;
ans+=1ll*(v[b].sz)*(v[b].sz-1);
set<int> nxt;
for(auto y:v[a].tp){
int u=find(y);
if(u==b){
continue;
}
if(v[u].tb.find(b)!=v[u].tb.end()){
nxt.insert(u);
}
}
for(auto y:v[a].fp){
int u=find(y);
if(u==b){
continue;
}
if(v[u].fb.find(b)!=v[u].fb.end()){
nxt.insert(u);
}
}
for(auto y:v[a].tb){
if(y.fs!=b){
v[b].tb[y.fs]++;
}
}
for(auto y:v[a].fb){
if(y.fs!=b){
v[b].fb[y.fs]++;
}
}
for(auto h:nxt){
q.push({h,b});
}
}
}
signed main(){
AquA;
int n,m;
cin >> n >> m;
v.resize(n);
for(int i=0;i<n;i++){
v[i].bo=i;
v[i].sz=1;
v[i].ch.push_back(i);
}
for(int i=0;i<m;i++){
int a,b;
cin >> a >> b;
a--;
b--;
int c=find(a),d=find(b);
if(c==d){
cout << ans << "\n";
}
else{
if(v[d].tp.find(a)==v[d].tp.end()){
v[d].tp.insert(a);
ans+=v[d].sz;
v[d].tb[c]++;
v[c].fb[d]++;
v[c].fp.insert(b);
if(v[c].tb.find(d)!=v[c].tb.end()){
merge(a,b);
}
}
}
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
