Submission #932763

#	Time	Username	Problem	Language	Result	Execution time	Memory
932763		WongChun1234	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	2 ms	10840 KiB

joitter2

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100050;
const bool DEBUG=0;
int n,m,a,b,par[N],sz[N],inord[N],ans;
map<int,int> one[N],frm[N];
int find(int u){
	return par[u]=(par[u]==u?u:find(par[u]));
}
signed main(){
	cin>>n>>m;
	iota(par+1,par+n+1,1);
	for (int i=1;i<=n;i++) sz[i]=1;
	while (m--){
		cin>>a>>b;
		if (DEBUG) cout<<a<<"->"<<b<<"\n";
		if (find(a)==find(b)||one[find(b)][a]){
		    if (DEBUG) cout<<"ignore\n";
			//alr have a->b edge
		}else if (frm[find(a)][find(b)]){
			//union find(a) and find(b)
			if (DEBUG) cout<<"merge "<<find(a)<<" "<<find(b)<<"\n";
			a=find(a);
			b=find(b);
			if (DEBUG) cout<<"size "<<sz[a]<<" "<<sz[b]<<" frm "<<frm[a][b]<<"\n";
			if (DEBUG) cout<<"inord "<<inord[a]<<" "<<inord[b]<<"\n";
			ans+=sz[a]*sz[b]*2;
			ans-=sz[a]*frm[a][b];
			inord[a]-=frm[a][b];
			frm[a].erase(b);
			ans-=inord[a]*sz[a];
			ans-=inord[b]*sz[b];
			ans+=(inord[a]+inord[b])*(sz[a]+sz[b]);
			
			if (inord[a]<inord[b]){
			    swap(a,b);
			    if (DEBUG) cout<<"swap\n";
			}
			if (DEBUG) cout<<b<<"!\n";
			//insert b into a
			for (auto i:one[b]){
			    if (DEBUG) cout<<i.first<<"-->"<<b<<"\n";
				if (find(i.first)==b||find(i.first)==a) continue;
				if (one[a][i.first]){
					ans-=(sz[a]+sz[b]);
					inord[b]--;
					frm[b][find(i.first)]--;
				}else{
					one[a][i.first]=1;
				}
			}
			for (auto i:frm[b]){
			    frm[a][i.first]+=i.second;
			}
			if (DEBUG) cout<<"par["<<b<<"]="<<a<<"\n";
			sz[a]+=sz[b];
			par[b]=a;
		}else{
			ans+=sz[find(b)];
			one[find(b)][a]=1;
			frm[find(b)][find(a)]++;
			inord[find(b)]++;
		}
		cout<<ans<<"\n";
	}
}

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