제출 #1184226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184226		ttamx	자매 도시 (APIO20_swap)	C++20	0 / 100	74 ms	22656 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

const int N=200005;
const int LG=18;
const int INF=INT_MAX/2;

int n,m;
int fa[N],par[LG][N],a[N],dep[N];

int fp(int u){return fa[u]=u==fa[u]?u:fp(fa[u]);}

int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=LG-1;i>=0;i--)if(dep[par[i][u]]>=dep[v])u=par[i][u];
	if(u==v)return u;
	for(int i=LG-1;i>=0;i--)if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v];
	return par[0][u];
}

void init(int _n,int _m,vector<int> _u,vector<int> _v,vector<int> _w){
	n=_n,m=_m;
	vector<tuple<int,int,int>> e;
	for(int i=0;i<m;i++)e.emplace_back(_w[i],_u[i],_v[i]);
	sort(e.begin(),e.end());
	iota(fa,fa+2*n,0);
	fill(a,a+2*n,INF);
	int cur=n;
	for(auto [w,u,v]:e){
		u=fp(u),v=fp(v);
		if(u!=v){
			fa[u]=fa[v]=par[0][u]=par[0][v]=cur;
			if(min(a[u],a[v])<INF)a[cur]=w;
			cur++;
		}else{
			a[u]=min(a[u],w);
		}
	}
	par[0][cur-1]=cur-1;
	for(int i=cur-2;i>=0;i--){
		int p=par[0][i];
		dep[i]=dep[p]+1;
		a[i]=min(a[i],a[p]);
	}
	for(int i=1;i<LG;i++)for(int u=0;u<cur;u++)par[i][u]=par[i-1][par[i-1][u]];
}

int getMinimumFuelCapacity(int u,int v){
	return -1;
	int res=a[lca(u,v)];
	return res<INF?res:-1;
}

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