Submission #1249343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249343		anhkhoa	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	5 ms	9792 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
set<int> vao[100009],ra[100009];
int n,m,root[100009],num[100009];

int find(int u) {
	if(u!=root[u]) root[u]=find(root[u]);
	return root[u];
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;i++) {
		root[i]=i;
		num[i]=1;
	}
	long long ans=0;
	for (int i=1;i<=m;i++) {
		int u,v;
		cin>>u>>v;
		int rootu=find(u);
		int rootv=find(v);
		set<int>::iterator ret=vao[rootu].find(rootv);
		if(rootu==rootv||vao[rootv].find(rootu)!=vao[rootv].end()) {
			cout<<ans<<endl;
			continue;
		}
		if(ret==vao[rootu].end()) {
			ans+=num[rootv];
			ra[rootu].insert(rootv);
			vao[rootv].insert(rootu);
			//if(u==3&&v==4) cout<<"YES"<<endl;
		} else {
			ans+=num[rootv]*num[rootu];
	//	ans+=num[rootu]*num[rootv]-1;
			vao[rootu].erase(ret);
		//	ans-=vao[rootu].size();
		//	ans-=vao[rootv].size();
			ans+=num[rootu]*(vao[rootv].size());//+num[rootv]);
			ans+=num[rootv]*(vao[rootu].size());//+num[rootu]);
		//	cout<<ans<<endl;
			ra[rootu].insert(v);
			vao[rootv].insert(u);
			if(vao[rootu].size()+ra[rootu].size()<vao[rootv].size()+ra[rootv].size()) {
				swap(rootu,rootv);
			}
			root[rootv]=rootu;
			num[rootu]+=num[rootv];
			if(!vao[rootv].empty())
			for (set<int>::iterator it=vao[rootv].begin();it!=vao[rootv].end();it++) {
				vao[rootu].insert(*it);
			}
			if(!ra[rootv].empty())
			for (set<int>::iterator it=ra[rootv].begin();it!=ra[rootv].end();it++) {
				ra[rootu].insert(*it);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

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