제출 #556652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556652		UncoolAnon	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	1 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,answer=0;
	cin>>n>>m; vector<int> pr(n+1),c[n+1]; for(int i=1;i<=n;i++){pr[i]=i;c[i].push_back(i);}
	set<int> in[n+1],out[n+1]; 
	while(m--){
		int a,b; cin>>a>>b; 
		if(pr[a]==pr[b]){}
		else if(out[b].find(pr[a])==out[b].end()){
			answer-=in[pr[b]].size()*c[pr[b]].size(); 
			in[pr[b]].insert(a); 
			out[a].insert(pr[b]); 
			answer+=in[pr[b]].size()*c[pr[b]].size();
		}
		else{
			a=pr[a],b=pr[b]; 
			if(c[a].size()<c[b].size()) swap(a,b); 
			answer-=in[a].size()*c[a].size(); answer-=in[b].size()*c[b].size(); 
			answer+=2*c[a].size()*c[b].size(); 
			/*cout <<"------------------\n"; 
			cout << a << " " << b << endl ; 
			cout << in[a].size() << " " << in[b].size() << endl ; 
			cout << c[a].size() << " " << c[b].size() << endl ; 
			cout<<"--> ";*/
			pr[b]=a; 
			for(int x:in[b]){
				if(pr[x]!=a){
					in[a].insert(x); 
					out[x].erase(b); 
					out[x].insert(a); 
				}
				else{
					out[x].erase(b); 
				}
			}
			for(int x:c[b])if(out[x].find(a)!=out[x].end()){out[x].erase(a);in[a].erase(x);}
			for(int x : c[b]) c[a].push_back(x); 
			c[b].clear(); 
			answer+=in[a].size()*c[a].size(); 
		} 
		cout<<answer<<'\n'; 
	}
	return 0; 
}

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