제출 #954365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954365		amirhoseinfar1385	자매 도시 (APIO20_swap)	C++17	6 / 100	282 ms	46524 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
struct yal{
	int u,v,w,vas;
	bool operator <(yal b){
		return w<b.w;
	}
	int getad(int fu){
		return (fu^u^v);
	}
};
const int maxn=100000+10,lg=17;
int n,m,wlca[lg][maxn],lca[lg][maxn],inf=1e9+5,mainres[maxn],timea;
vector<yal>alle;
vector<int>adjt[maxn];
pair<int,int>stf[maxn];

bool zird(int u,int v){
	return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}

struct dsu{
	int par[maxn],val[maxn];
	vector<int>allv[maxn];
	dsu(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
			val[i]=inf;
			allv[i].push_back(i);
		}
	};
	int root(int u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}
	int con(int u,int v,int w){
		int rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			par[rootv]=rootu;
			if((int)allv[rootu].size()<(int)allv[rootv].size()){
				swap(allv[rootu],allv[rootv]);
			}
			for(auto x:allv[rootv]){
				allv[rootu].push_back(x);
			}
			if(val[rootu]<inf||val[rootv]<inf){
				val[rootu]=w;
			}
			if(val[rootu]<inf){
				for(auto x:allv[rootu]){
					mainres[x]=min(mainres[x],val[rootu]);
				}
				allv[rootu].clear();
			}
			return 1;
		}else{
			return 0;
		}
	}
	void tagh(int u,int w){
		u=root(u);
		for(auto x:allv[u]){
			mainres[x]=min(mainres[x],w);
		}
		allv[u].clear();
		val[u]=min(w,val[u]);
	}
}ds;
int av=inf;

void dfs(int u=1,int par=-1){
	timea++;
	stf[u].first=timea;
	for(auto x:adjt[u]){
		int v=alle[x].getad(u);
		if(v==par){
			continue;
		}
		wlca[0][v]=alle[x].w;
		lca[0][v]=u;
		dfs(v,u);
	}
	stf[u].second=timea;
}

void callca(){
	for(int i=1;i<lg;i++){
		for(int j=1;j<=n;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
			wlca[i][j]=max(wlca[i-1][j],wlca[i-1][lca[i-1][j]]);
		}
	}
}

int getlca(int u,int v){
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(int i=lg-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			u=lca[i][u];
		}
	}
	return lca[0][u];
}

int getwlca(int u,int v){
	if(u==v){
		return 0;
	}
	int ret=0;
	for(int i=lg-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			ret=max(ret,wlca[i][u]);
			u=lca[i][u];
		}
	}
	ret=max(ret,wlca[0][u]);
	return ret;
}

void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n=N;
	m=M;
	alle.resize(m);
	for(int i=0;i<maxn;i++){
		mainres[i]=inf;
	}
	for(int i=0;i<m;i++){
		alle[i].u=U[i];
		alle[i].v=V[i];
		alle[i].w=W[i];
	}
	sort(alle.begin(),alle.end());
	for(int i=0;i<m;i++){
		if(ds.con(alle[i].u,alle[i].v,alle[i].w)){
			alle[i].vas=1;
			adjt[alle[i].u].push_back(i);
			adjt[alle[i].v].push_back(i);
			if((int)adjt[alle[i].u].size()>2||(int)adjt[alle[i].v].size()>2){
				ds.tagh(alle[i].u,alle[i].w);
			}
		}else{
			ds.tagh(alle[i].u,alle[i].w);
		}
	}
	dfs();
	callca();
}
int mx;
void dfsres(int u,int v){
	int uv=getlca(u,v);
	mx=max(getwlca(u,uv),getwlca(v,uv));
}

int getMinimumFuelCapacity(int X, int Y) {
  mx=inf;
  dfsres(X,Y);
  long long ret=max(mx,min(mainres[X],mainres[Y]));
  if(ret>=inf){
  	return -1;
  }
  return ret;
}

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