oj.uz

답안 #932767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932767 2024-02-24T07:27:15 Z WongChun1234 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++14
0 / 100
 2 ms 10840 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100050;
const bool DEBUG=0;
int n,m,a,b,par[N],sz[N],inord[N],ans;
map<int,int> one[N],frm[N];
int find(int u){
	return par[u]=(par[u]==u?u:find(par[u]));
}
signed main(){
	cin>>n>>m;
	iota(par+1,par+n+1,1);
	for (int i=1;i<=n;i++) sz[i]=1;
	while (m--){
		cin>>a>>b;
		if (DEBUG) cout<<a<<"->"<<b<<"\n";
		if (find(a)==find(b)||one[find(b)][a]){
		    if (DEBUG) cout<<"ignore\n";
			//alr have a->b edge
		}else if (frm[find(a)][find(b)]){
			//union find(a) and find(b)
			if (DEBUG) cout<<"merge "<<find(a)<<" "<<find(b)<<"\n";
			a=find(a);
			b=find(b);
			if (DEBUG) cout<<"size "<<sz[a]<<" "<<sz[b]<<" frm "<<frm[a][b]<<"\n";
			if (DEBUG) cout<<"inord "<<inord[a]<<" "<<inord[b]<<"\n";
			ans+=sz[a]*sz[b]*2;
			ans-=sz[a]*frm[a][b];
			inord[a]-=frm[a][b];
			frm[a].erase(b);
			ans+=inord[a]*sz[b];
			ans+=inord[b]*sz[a];
			
			if (1||inord[a]<inord[b]){
			    swap(a,b);
			    if (DEBUG) cout<<"swap\n";
			}
			if (DEBUG) cout<<b<<"!\n";
			//insert b into a
			for (auto i:one[b]){
			    if (DEBUG) cout<<i.first<<"-->"<<b<<"\n";
				if (find(i.first)==b||find(i.first)==a) continue;
				if (one[a][i.first]){
					ans-=(sz[a]+sz[b]);
					inord[b]--;
					frm[b][find(i.first)]--;
				}else{
					one[a][i.first]=1;
				}
			}
			for (auto i:frm[b]){
			    frm[a][find(i.first)]+=i.second;
			}
			if (DEBUG) cout<<"par["<<b<<"]="<<a<<"\n";
			inord[a]+=inord[b];
			sz[a]+=sz[b];
			par[b]=a;
		}else{
			ans+=sz[find(b)];
			one[find(b)][a]=1;
			frm[find(b)][find(a)]++;
			inord[find(b)]++;
		}
		cout<<ans<<"\n";
	}
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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