Submission #556295

#	Time	Username	Problem	Language	Result	Execution time	Memory
556295		UncoolAnon	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++14	0 / 100	11 ms	16564 KiB

joitter2

#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 (stderr)

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83