제출 #877122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
877122		amirhoseinfar1385	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	3 ms	11352 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int n,m;

struct dsu{
	int par[maxn],sz[maxn],szkho[maxn],szvo[maxn];
	long long res=0;
	set<int>vorod[maxn],khoroj[maxn];
	dsu(){
		for(int i=1;i<maxn;i++){
			par[i]=i;
			sz[i]=1;
		}
	};
	int root(int u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}
	void con(int u,int v){
		u=root(u);v=root(v);
	//	cout<<"con: "<<u<<" "<<v<<" "<<sz[u]<<" "<<sz[v]<<"\n";
		if(u==v){
			return ;
		}
		vector<pair<int,int>>allq;
		if(sz[u]==1&&sz[v]==1){
			for(auto x:vorod[u]){
				res--;
				khoroj[x].erase(u);
				allq.push_back(make_pair(x,u));
			}
			for(auto x:khoroj[u])
			{
				res-=sz[x];
				szvo[x]--;
				vorod[x].erase(u);
				allq.push_back(make_pair(u,x));
			}
			for(auto x:vorod[v]){
				res--;
				khoroj[x].erase(v);
				allq.push_back(make_pair(x,v));
			}
			for(auto x:khoroj[v])
			{
				res-=sz[x];
				szvo[x]--;
				vorod[x].erase(v);
				allq.push_back(make_pair(v,x));
			}
			res+=2;
			vorod[u].clear();
			khoroj[u].clear();
			vorod[v].clear();
			khoroj[v].clear();
			par[u]=v;
			sz[v]+=sz[u];
			szvo[u]=szvo[v]=szkho[u]=szkho[v]=0;
		}
		else if(sz[u]==1||sz[v]==1){
			if(sz[v]==1){
				swap(u,v);
			}
			for(auto x:vorod[u]){
				res--;
				khoroj[x].erase(u);
				allq.push_back(make_pair(x,u));
			}
			for(auto x:khoroj[u])
			{
				res-=sz[x];
				szvo[x]--;
				vorod[x].erase(u);
				allq.push_back(make_pair(u,x));
			}
	//		cout<<"salam: "<<res<<" "<<szkho[v]<<" "<<szvo[v]<<"\n";
			res+=2ll*sz[v]*sz[u];
			res+=1ll*sz[u]*(szkho[v]+szvo[v]);
			sz[v]+=1;
			par[u]=v;
			vorod[u].clear();
			khoroj[u].clear();
		}
		else{
			if(sz[u]>sz[v]){
				swap(u,v);
			}
			for(auto x:vorod[u]){
				res-=1ll*sz[u]*sz[x];
				khoroj[x].erase(u);
				allq.push_back(make_pair(x,u));
			}
			for(auto x:khoroj[u]){
				res-=1ll*sz[u]*sz[x];
				vorod[x].erase(u);
				allq.push_back(make_pair(u,x));
			}
			res+=1ll*sz[u]*sz[v]*2;
			res+=1ll*sz[u]*(szkho[v]+szvo[v]);
			vorod[u].clear();
			khoroj[u].clear();
			sz[v]+=sz[u];
			par[u]=v;
		}
		for(auto x:allq){
			add(x.first,x.second);
		}
	}	
	void add(int u,int v){
		u=root(u);
		v=root(v);
	//	cout<<"add: "<<u<<" "<<v<<" "<<sz[u]<<" "<<sz[v]<<"\n";
		if(u==v){
			return ;
		}		
		if(sz[u]==sz[v]&&sz[u]==1){
			if(khoroj[u].count(v)!=0){
				return ;
			}
			res++;
			khoroj[u].insert(v);
			vorod[v].insert(u);
			szvo[v]++;
			if(khoroj[v].count(u)!=0){
				con(u,v);
			}
		}
		else if(sz[u]==1){
			if(khoroj[u].count(v)!=0){
				return ;
			}
			res+=sz[v];
			khoroj[u].insert(v);
			vorod[v].insert(u);
			szvo[v]++;
		//	cout<<"inja: "<<v<<" "<<szvo[v]<<"\n";
			if(vorod[u].count(v)!=0){
				con(u,v);
			}
		}
		else if(sz[v]==1){
			if(vorod[v].count(u)!=0){
				return ;
			}
			res++;
			vorod[v].insert(u);
			szvo[v]+=sz[u];
			if(khoroj[v].count(u)!=0){
				con(u,v);
			}
		}
		else{
			if(khoroj[u].count(v)!=0){
				return ;
			}
			res+=sz[u]*sz[v];
			vorod[v].insert(u);
			khoroj[u].insert(v);
			szvo[v]+=sz[u];
			szkho[u]+=sz[v];
			if(vorod[u].count(v)!=0){
				con(u,v);
			}
		}
	}
}ds;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		ds.add(u,v);
		cout<<ds.res<<"\n";
	}	
}

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