#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long int llint;
llint p[100005],sz[100005],cnt[100005],r;
multiset <int> in[100005],in2[100005],out[100005];
set <pair<int,int> > s;
int find_par(int x) {
if(x==p[x]) return x;
int p1=find_par(p[x]);
p[x]=p1;
return p1;
}
void edge(int a,int b) {
if(a==b) return;
if(out[a].find(b)!=out[a].end()) return;
in[b].insert(a);
out[a].insert(b);
cnt[b]+=sz[b];
r+=sz[b];
if(out[b].find(a)!=out[b].end()) {
while(in[b].find(a)!=in[b].end()) {
in[b].erase(in[b].find(a));
cnt[b]-=sz[b];
r-=sz[b];
}
while(in[a].find(b)!=in[a].end()) {
in[a].erase(in[a].find(b));
cnt[a]-=sz[a];
r-=sz[a];
}
out[b].erase(a);
out[a].erase(b);
s.insert(make_pair(a,b));
}
}
void f(int x,int y) {
x=find_par(x);
y=find_par(y);
if(x==y) return;
//cout << " " << r << "\n";
if(in[x].size()+out[x].size()<in[y].size()+out[y].size()) swap(x,y);
for(multiset <int>::iterator it=in[y].begin();it!=in[y].end();) {
int a=(*it);
out[a].erase(y);
edge(a,x);
it=in[y].erase(it);
}
for(multiset <int>::iterator it=out[y].begin();it!=out[y].end();) {
int a=(*it);
in[a].erase(y);
edge(x,a);
it=out[y].erase(it);
}
for(multiset <int>::iterator it=in2[y].begin();it!=in2[y].end();it++) {
in2[x].insert((*it));
//cout << (*it) << "\n";
}
//cout << " " << r << " " << cnt[x]+cnt[y] << "\n";
r-=sz[x]*(sz[x]-1);
r-=sz[y]*(sz[y]-1);
r-=cnt[x];
r-=cnt[y];
sz[x]+=sz[y];
r+=sz[x]*(sz[x]-1);
cnt[x]=in[x].size()*sz[x];
//cout << " " << r << "\n";
r+=cnt[x];
in[y].clear();
in2[y].clear();
out[y].clear();
p[y]=x;
//cout << " " << r << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
llint n,m,e=0;
cin >> n >> m;
for(int i=0;i<n;i++) {
p[i]=i;
sz[i]=1;
}
for(int i=0;i<m;i++) {
int x,y;
cin >> x >> y;
int x1=x-1,y1=y-1;
x=find_par(x-1);
y=find_par(y-1);
if(out[x].find(y)!=out[x].end() && in2[y].find(x1)==in2[y].end()) {
//cout << "abc\n";
in2[y].insert(x1);
out[x].insert(y);
in[y].insert(x);
r+=sz[y];
cnt[y]+=sz[y];
}
else if(x!=y) in2[y].insert(x1);
edge(x,y);
while(!s.empty()) {
int a=(*s.begin()).first,b=(*s.begin()).second;
s.erase(s.begin());
f(a,b);
}
cout << r << "\n";
/*for(int j=0;j<n;j++) {
cout << find_par(j) << " ";
}
cout << "\n";*/
}
return 0;
}
/*
__
/\ \
/ \ \
/ /\ \ \
/ / /\ \ \
/ / /__\_\ \
/ / /________\
\/___________/
*/
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:90:14: warning: unused variable 'y1' [-Wunused-variable]
90 | int x1=x-1,y1=y-1;
| ^~
joitter2.cpp:81:12: warning: unused variable 'e' [-Wunused-variable]
81 | llint n,m,e=0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14420 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
