Submission #1249356

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

joitter2

#include<bits/stdc++.h>
using namespace std;
int n,m,root[100009],num[100009],ans=0;
vector<pair<int,int>>cannoi;
set<int>childe[100009],vao[100009],ra[100009];
int find(int u) {
	if(u!=root[u]) root[u]=find(root[u]);
	return root[u];
}

void add(int u,int v) {
	ra[u].insert(v);
	vao[v].insert(u);
	if(ra[v].find(u)!=ra[v].end()) {
		cannoi.push_back({u,v});
	}
	return ;
}

void noi(int u,int v) {
	if(childe[u].size()+vao[u].size()+ra[u].size()<childe[v].size()+vao[v].size()+ra[v].size()) {
		swap(u,v);
	}
	ans+=childe[u].size()*num[v]+childe[v].size()*num[u];
	root[v]=u;
	num[u]+=num[v];
	set<int>::iterator vu=vao[u].find(v),ru=ra[u].find(v),vv=vao[v].find(u),rv=ra[v].find(u);
	if(vu!=vao[u].end()) {
		vao[u].erase(vu);
	}
	if(ru!=ra[u].end()) {
		ra[u].erase(ru);
	}
	if(vv!=vao[v].end()) {
		vao[v].erase(vv);
	}
	if(rv!=ra[v].end()) {
		ra[v].erase(rv);
	}
	for (set<int>::iterator it=childe[v].begin();it!=childe[v].end();it++) {
		if(childe[u].find(*it)!=childe[u].end()) {
			ans-=num[u];
		} else {
			childe[u].insert(*it);
		}
	}
	childe[v].clear();
	for (set<int>::iterator it=vao[v].begin();it!=vao[v].end();it++) {
		if(ra[*it].find(v)!=ra[*it].end()) {
			ra[*it].erase(ra[*it].find(v));
		}
		add(*it,u);
	}
	for (set<int>::iterator it=ra[v].begin();it!=ra[v].end();it++) {
		if(vao[*it].find(v)!=vao[*it].end()) {
			vao[*it].erase(vao[*it].find(v));
		}
		add(u,*it);
	}
	return ;
}

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;
		childe[i].insert(i);
	}
	for (int i=1;i<=m;i++) {
		int u,v;
		cin>>u>>v;
		int rootu=find(u);
		int rootv=find(v);
		if(rootu==rootv||childe[rootv].find(u)!=childe[rootv].end()) {
			cout<<ans<<'\n';
			continue;
		}
		ans+=num[rootv];
		childe[rootv].insert(u);
		add(rootu,rootv);
		while(!cannoi.empty()) {
			pair<int ,int> ret=cannoi.back();
			cannoi.pop_back();
			noi(u,v);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

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