Submission #213134

#	Time	Username	Problem	Language	Result	Execution time	Memory
213134		username	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	871 ms	61048 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]);
}

void merge(int pa,int pb){
	pa=find(pa),pb=find(pb);
	if(pa==pb)return;
	res-=sz[pa]*re[pa]->size();
	res-=sz[pb]*re[pb]->size();
	while(1){
		auto it=ex[pa]->lower_bound({pb,0});
		if(it!=ex[pa]->end()&&it->f==pb)ex[pa]->erase(it);
		else break;
	}
	while(1){
		auto it=re[pa]->lower_bound({pb,0});
		if(it!=re[pa]->end()&&it->f==pb)re[pa]->erase(it);
		else break;
	}
	while(1){
		auto it=ex[pb]->lower_bound({pa,0});
		if(it!=ex[pb]->end()&&it->f==pa)ex[pb]->erase(it);
		else break;
	}
	while(1){
		auto 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(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});
	}
	vector<int>nx;
	tr(x,*ex[pa]){
		auto it=re[pb]->lower_bound({x.f,0});
		if(it!=re[pb]->end()&&it->f==x.f)nx.pb(x.f);
		ex[pb]->insert(x);
	}
	tr(x,*re[pa]){
		auto it=ex[pb]->lower_bound({x.f,0});
		if(it!=ex[pb]->end()&&it->f==x.f)nx.pb(x.f);
		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,nx.size())merge(pb,nx[i]);
}

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){
			merge(pa,pb);
		}
//		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: In function 'void merge(int_fast64_t, int_fast64_t)':
joitter2.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
joitter2.cpp:97:2: note: in expansion of macro 'REP'
  REP(i,0,nx.size())merge(pb,nx[i]);
  ^~~
joitter2.cpp: At global scope:
joitter2.cpp:100:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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