Submission #213124

#	Time	Username	Problem	Language	Result	Execution time	Memory
213124		username	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	5 ms	384 KiB

joitter2

#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 (stderr)

joitter2.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83