제출 #556294

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

joitter2

#include <bits/stdc++.h>
#define int long long
using namespace std; 
signed main(){
	ios_base::sync_with_stdio(0); 
    cin.tie(nullptr); 
	int n,m;
	cin>>n>>m; 
	set<int> in[n+1],out[n+1]; 
	vector<int> pr(n+1),sz(n+1,1); for(int i=1;i<=n;i++) pr[i]=i; 
	auto find=[&](int a){
		while(a!=pr[a]){
			pr[a]=pr[pr[a]]; 
			a=pr[a]; 
		}
		return a;
	}; 
	int answer=0; 
	while(m--){
		int a,b; 
		cin>>a>>b; 
		a=find(a),b=find(b); 
		if(out[b].find(a)==out[b].end()){
			out[a].insert(b); 
			answer-=in[b].size()*sz[b]; 
			in[b].insert(a); 
			answer+=in[b].size()*sz[b];
		}
		else{
			answer-=in[b].size()*sz[b]; 
			answer-=in[a].size()*sz[a]; 
			if(sz[a]<sz[b]) swap(a,b); 
			answer+=sz[a]*sz[b]*2; 
			pr[b]=a; 
			sz[a]+=sz[b];
			for(int x : in[b]){
				if(x!=a){
					in[a].insert(x); 
					out[x].erase(b); 
					out[x].insert(a); 
				}
				else{
					out[a].erase(b); 
				}
			}
			for(int x:out[b]){
				if(x!=a){
					out[a].insert(x);
					in[x].erase(b); 
					in[x].insert(a); 
				}
				else{
					in[a].erase(b);
				}
			}
			out[b].clear(); 
			in[b].clear(); 
			answer+=in[a].size()*sz[a]; 
		}
		cout<<answer<<'\n'; 
	} 
	return 0; 
}

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