oj.uz

답안 #556295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556295 2022-05-02T19:24:07 Z UncoolAnon 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 11 ms 16564 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std; 
signed main(){
	#ifndef ONLINE_JUDGE
		freopen("in.txt","r",stdin);
		freopen("outie.txt","w",stdout); 
	#endif 
	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]; 
			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; 
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:6:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |   freopen("in.txt","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~
joitter2.cpp:7:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |   freopen("outie.txt","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 16564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 16564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 16564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -