제출 #328027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
328027		kshitij_sodani	자매 도시 (APIO20_swap)	C++14	37 / 100	2089 ms	33880 KiB

swap

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second

#include "swap.h"


int n,m;
int val=0;
vector<pair<int,pair<int,int>>> ed;
int par[100001];
int ss[100001];
int tt[100001];
int dd[100001];
multiset<int> xx[100001];
vector<int> comp[100001];
int ans[100001];

int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
void upd(int x,int y){
	int stt=0;

	if(ss[x]>tt[x]-1){
		stt=1;
	}
	auto ee=xx[x].end();
	ee--;
	if(*ee>=3){
		stt=1;
	}
	if(stt){
		for(auto j:comp[x]){
			if(ans[j]==-1){
				ans[j]=y;
			}
		}
	}


}
void init(int nn, int mm,vector<int> aa,vector<int> bb,vector<int> cc) {
	m=mm;
	n=nn;
	for(int i=0;i<m;i++){
		ed.pb({cc[i],{aa[i],bb[i]}});
	}
	sort(ed.begin(),ed.end());
	for(int i=0;i<n;i++){
		par[i]=i;
		ss[i]=0;
		dd[i]=0;
		xx[i].clear();
		tt[i]=1;
		xx[i].insert(0);
		ans[i]=-1;
		comp[i].pb(i);
	}
	for(auto j:ed){
		int x=find(j.b.a);
		int y=find(j.b.b);
		if(x==y){
			ss[x]+=1;
			auto jj=xx[x].find(dd[j.b.a]);
			xx[x].erase(jj);
			dd[j.b.a]+=1;
			xx[x].insert(dd[j.b.a]);

			jj=xx[x].find(dd[j.b.b]);
			xx[x].erase(jj);
			dd[j.b.b]+=1;
			xx[x].insert(dd[j.b.b]);
			if(ans[x]==-1){
				upd(x,j.a);
			}
		}
		else{
			if(xx[x].size()<xx[y].size()){
				swap(x,y);
			}
			par[y]=x;
			for(auto jj:xx[y]){
				xx[x].insert(jj);
			}
			for(auto jj:comp[y]){
				comp[x].pb(jj);
				if(ans[x]!=-1 and ans[jj]==-1){
					ans[jj]=j.a;
				}
			}
			xx[y].clear();
			ss[x]+=ss[y]+1;
			tt[x]+=tt[y];
			
			auto jj=xx[x].find(dd[j.b.a]);
			xx[x].erase(jj);
			dd[j.b.a]+=1;
			xx[x].insert(dd[j.b.a]);

			jj=xx[x].find(dd[j.b.b]);
			xx[x].erase(jj);
			dd[j.b.b]+=1;
			xx[x].insert(dd[j.b.b]);
			if(ans[x]==-1){
				upd(x,j.a);
			}
		}
	}
	/*for(int i=0;i<n;i++){
		cout<<ans[i]<<":";
	}
	cout<<endl;*/
}
/*vector<int> adj[100001];
int vis[100001];
int st=1;
void dfs(int no,int par=-1){
	vis[no]=1;
	if(adj[no].size()>2){
		st=0;
	}
	for(auto j:adj[no]){
		if(j==par){
			continue;
		}
		if(vis[j]==0){
			dfs(j,no);
		}
		else{
			st=0;
		}
	}
}*/
int getMinimumFuelCapacity(int aa, int bb) {
	if(ans[aa]==-1 or ans[bb]==-1){
		return -1;
	}
	int tot=max(ans[aa],ans[bb]);
	for(int i=0;i<n;i++){
		par[i]=i;
		ss[i]=0;
		dd[i]=0;
		xx[i].clear();
		tt[i]=1;
		xx[i].insert(0);
		comp[i].clear();
		comp[i].pb(i);
	}
	for(auto j:ed){
		int x=find(j.b.a);
		int y=find(j.b.b);
		if(x==y){
			ss[x]+=1;
			auto jj=xx[x].find(dd[j.b.a]);
			xx[x].erase(jj);
			dd[j.b.a]+=1;
			xx[x].insert(dd[j.b.a]);

			jj=xx[x].find(dd[j.b.b]);
			xx[x].erase(jj);
			dd[j.b.b]+=1;
			xx[x].insert(dd[j.b.b]);
		}
		else{
			if(xx[x].size()<xx[y].size()){
				swap(x,y);
			}
			par[y]=x;
			for(auto jj:xx[y]){
				xx[x].insert(jj);
			}
			for(auto jj:comp[y]){
				comp[x].pb(jj);
			}
			comp[y].clear();
			xx[y].clear();
			ss[x]+=ss[y]+1;
			tt[x]+=tt[y];
			
			auto jj=xx[x].find(dd[j.b.a]);
			xx[x].erase(jj);
			dd[j.b.a]+=1;
			xx[x].insert(dd[j.b.a]);

			jj=xx[x].find(dd[j.b.b]);
			xx[x].erase(jj);
			dd[j.b.b]+=1;
			xx[x].insert(dd[j.b.b]);
		}
		if(find(aa)==find(bb)){
			return max(tot,j.a);
		}
	}








	return -1;
	//return ac;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27