Submission #550293

#	Time	Username	Problem	Language	Result	Execution time	Memory
550293		Antekb	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	0 / 100	6 ms	9684 KiB

joitter2

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int r[N];
using ll = long long;
ll ans=0;
bool czy[N];
int ile=0;
set<int> S[N], co[N];
int find(int i){
	if(i==r[i])return i;
	return r[i]=find(r[i]);
}
void Union(int a,int b){
	if(a==b)return;
	if(S[a].size()+co[a].size()>S[b].size()+co[b].size())swap(a, b);
	ans-=S[a].size()*1ll*co[a].size();
	ans-=S[b].size()*1ll*co[b].size();
	for(int i:S[a])if(co[b].find(i)!=co[b].end() && !czy[i])czy[i]=1, ile++;
	for(int i:co[a])if(S[b].find(i)!=S[b].end() && !czy[i])czy[i]=1, ile++;
	for(int i:S[a])S[b].insert(i);
	for(int i:co[a])co[b].insert(i);
	ans+=S[b].size()*1ll*co[b].size();
	r[a]=b;
}
int main(){
	int n, q;
	cin>>n>>q;
	for(int i=1; i<=n; i++)r[i]=i, co[i].insert(i);
	while(q--){
		int u, v;
		cin>>u>>v;
		int vv=v;
		v=find(v);
		if(S[v].find(u)==S[v].end()){
			//cout<<"a";
			S[v].insert(u);
			ans+=co[v].size();
			if(v==find(u) && !czy[u])czy[u]=1, ile++;
		}
		if(S[find(u)].find(vv)!=S[find(u)].end()){
			//cout<<"b";
			Union(find(u), v);
		}
		cout<<ans-ile<<"\n";
	}
}

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