oj.uz

답안 #556570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556570 2022-05-03T11:07:06 Z UncoolAnon 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
using namespace std; 
int main(){
	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(a==b){}
		else 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]; 
			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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -