#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define tr(it,a) for(auto it:a)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define umin(x,y) (x=min(x,(y)))
#define umax(x,y) (x=max(x,(y)))
#define mid ((l+r)/2)
#define lch (idx*2+1)
#define rch (idx*2+2)
//
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define RREP(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define endl '\n'
// #define __db
#ifdef __db
#define IOS
#define prt(...) cerr<<__VA_ARGS__
#define ary(s,t)\
for(auto it=(s);it!=(t);++it)prt(*it<<" ");\
prt(endl);
#else
#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
#define prt(...)
#define ary(...)
#endif
//
const int maxn=1e5+9,maxm=3e5+9;
int n,m,res=0,fa[maxn],sz[maxn];
set<pii>*ex[maxn],*re[maxn];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
main(){
IOS;
cin>>n>>m;
REP(i,0,n)fa[i]=i,sz[i]=1,ex[i]=new set<pii>,re[i]=new set<pii>;
while(m--){
int a,b,pa,pb;cin>>a>>b,--a,--b,pa=find(a),pb=find(b);
if(pa==pb||ex[pa]->count({pb,a})){
cout<<res<<endl;
continue;
}
ex[pa]->insert({pb,a});
re[pb]->insert({pa,a});
res+=sz[pb];
auto it=ex[pb]->lower_bound({pa,0});
if(it!=ex[pb]->end()&&it->f==pa){
res-=sz[pa]*re[pa]->size();
res-=sz[pb]*re[pb]->size();
while(1){
it=ex[pa]->lower_bound({pb,0});
if(it!=ex[pa]->end()&&it->f==pb)ex[pa]->erase(it);
else break;
}
while(1){
it=re[pa]->lower_bound({pb,0});
if(it!=re[pa]->end()&&it->f==pb)re[pa]->erase(it);
else break;
}
while(1){
it=ex[pb]->lower_bound({pa,0});
if(it!=ex[pb]->end()&&it->f==pa)ex[pb]->erase(it);
else break;
}
while(1){
it=re[pb]->lower_bound({pa,0});
if(it!=re[pb]->end()&&it->f==pa)re[pb]->erase(it);
else break;
}
if(ex[pa]->size()+re[pa]->size()>ex[pb]->size()+re[pb]->size())swap(a,b),swap(pa,pb);
tr(x,*ex[pa]){
re[x.f]->erase({pa,x.s});
re[x.f]->insert({pb,x.s});
}
tr(x,*re[pa]){
ex[x.f]->erase({pa,x.s});
ex[x.f]->insert({pb,x.s});
}
tr(x,*ex[pa])ex[pb]->insert(x);
tr(x,*re[pa])re[pb]->insert(x);
res+=2*sz[pa]*sz[pb];
res+=(sz[pa]+sz[pb])*re[pb]->size();
fa[pa]=pb,sz[pb]+=sz[pa];
}
// REP(i,0,n){
// cout<<i+1<<"->"<<find(i)+1<<endl;
// }
// REP(i,0,n){
// if(i==find(i)){
// cout<<i+1<<":";
// tr(it,*ex[i])cout<<it.f+1<<","<<it.s+1<<" ";cout<<endl;
// tr(it,*re[i])cout<<it.f+1<<","<<it.s+1<<" ";cout<<endl;
// }
// }
// cout<<endl;
cout<<res<<endl;
}
}
Compilation message
joitter2.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
