/*#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100050;
set<int> all[N],E[N],R[N];
int my[N],sz[N],in_sz[N],out_sz[N];
ll ans;
ll Calc(int cmp){
return (ll)sz[cmp]*(sz[cmp]-1)+(ll)in_sz[cmp]*sz[cmp];
}
void Del(int cmp){
ans-=Calc(cmp);
}
void Add(int cmp){
ans+=Calc(cmp);
}
int main(){
int n,m;scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++)all[i].insert(i),my[i]=i,sz[i]=1;
for(int i=1;i<=m;i++){
int u,v;scanf("%i %i",&u,&v);
if(E[my[v]].count(my[u])){
int A=my[u],B=my[v];
ans+=sz[B]*sz[A];
printf("sz sz %lld\n",ans);
E[B].erase(A);out_sz[B]-=sz[A];
R[A].erase(B);in_sz[A]-=sz[B];
if(all[A].size()+E[A].size()+R[A].size()>all[B].size()+E[B].size()+R[B].size())swap(A,B);
printf("A(%i) in %i out %i sz %i\n",A,in_sz[A],out_sz[A],sz[A]);
printf("B(%i) in %i out %i sz %i\n",B,in_sz[B],out_sz[B],sz[B]);
for(int x:all[A]){
all[B].insert(x);
my[x]=B;
}
all[A].clear();
int AB=out_sz[B],BA=0;
for(int x:E[A]){
R[x].erase(A);
if(E[B].count(x)){
AB-=sz[x];
}else{
BA+=sz[x];
E[B].insert(x);
R[x].insert(B);
}
}
E[A].clear();
ans+=(ll)sz[A]*AB;
ans+=(ll)sz[B]*BA;
printf("out %lld\n",ans);
out_sz[B]+=BA;
AB=in_sz[B],BA=0;
for(int x:R[A]){
E[x].erase(A);
if(R[B].count(x)){
AB-=sz[x];
}else{
BA+=sz[x];
R[B].insert(x);
E[x].insert(B);
}
}
R[A].clear();
ans+=(ll)sz[A]*AB;
ans+=(ll)sz[B]*BA;
printf("in %lld\n",ans);
in_sz[B]+=BA;
sz[B]+=sz[A];
}else{
int A=my[u],B=my[v];
if(!E[A].count(B)){
ans+=(ll)sz[A]*sz[B];
E[A].insert(B);out_sz[A]+=sz[B];
R[B].insert(A);in_sz[B]+=sz[A];
}
}
printf("%lld\n",ans);
}
return 0;
}*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
set<int> in[N],all[N],E[N],R[N];
int my[N];
ll ans;
ll Calc(int cmp){
return (ll)all[cmp].size()*((int)all[cmp].size()-1)+(ll)in[cmp].size()*all[cmp].size();
}
void Del(int cmp){
ans-=Calc(cmp);
}
void Add(int cmp){
ans+=Calc(cmp);
}
int Mrg(int A,int B){
if(all[A].empty())return B;
if(all[B].empty())return A;
//printf("Mrg %i %i\n",A,B);
Del(A);Del(B);
E[B].erase(A);
R[A].erase(B);
E[A].erase(B);
R[B].erase(A);
if(all[A].size()+in[A].size()+E[A].size()+R[A].size()>all[B].size()+in[B].size()+E[B].size()+R[B].size())swap(A,B);
for(int x:all[A]){
if(in[B].count(x))in[B].erase(x);
all[B].insert(x);
my[x]=B;
}
all[A].clear();
for(int x:in[A]){
if(!all[B].count(x))in[B].insert(x);
}
in[A].clear();
vector<int> nxt;
for(int x:E[A]){
if(R[B].count(x))nxt.pb(x);
R[x].erase(A);
if(!E[B].count(x)){
E[B].insert(x);
R[x].insert(B);
}
}
E[A].clear();
for(int x:R[A]){
if(E[B].count(x))nxt.pb(x);
E[x].erase(A);
if(!R[B].count(x)){
R[B].insert(x);
E[x].insert(B);
}
}
R[A].clear();
Add(B);
sort(nxt.begin(),nxt.end());
nxt.erase(unique(nxt.begin(),nxt.end()),nxt.end());
//for(int x:nxt){
// if(B!=x)B=Mrg(B,x);
//}
return B;
}
int main(){
int n,m;scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++)all[i].insert(i),my[i]=i;
for(int i=1;i<=m;i++){
int u,v;scanf("%i %i",&u,&v);
int A=my[u],B=my[v];
if(A==B)continue;
Del(B);
in[B].insert(u);
E[A].insert(B);
R[B].insert(A);
Add(B);
for(int i=1;i<=n;i++){
if(E[i].count(my[u])&&E[my[u]].count(i)){
Mrg(i,my[u]);
}
if(E[i].count(my[v])&&E[my[v]].count(i)){
Mrg(i,my[v]);
}
}
printf("%lld\n",ans);
}
return 0;
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:147:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n,m;scanf("%i %i",&n,&m);
~~~~~^~~~~~~~~~~~~~~
joitter2.cpp:150:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u,v;scanf("%i %i",&u,&v);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
