| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1342679 | yc11 | 자매 도시 (APIO20_swap) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include<swap.h>
using namespace std;
vector<pair<int,int> > p;
vector<int> depth;
vector<vector<pair<int,int> > > n1;
void dfs(int x, int pa){
for (int i = 0;i<n1[x].size();i++){
if (n1[x][i].first==pa) continue;
depth[n1[x][i].first] = depth[x]+1;
p[n1[x][i].first] = make_pair(x,n1[x][i].second);
dfs(n1[x][i].first,x);
}
}
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
p.resize(N);
n1.resize(N);
depth.resize(N);
for (int i = 0;i<M;i++){
n1[U[i]].push_back(make_pair(V[i],W[i]));
n1[V[i]].push_back(make_pair(U[i],W[i]));
}
depth[0] = 0;
dfs(0,-1);
}
int getMinimumFuelCapacity(int X, int Y) {
if (depth[Y]>depth[X]) swap(X,Y);
int ans = 0;
int ans1 = 1e9+1;
vector<int> path;
vector<int> path1;
path1.push_back(Y);
path.push_back(X);
while (depth[X]!=depth[Y]) {
ans = max(ans,p[X].second);
X = p[X].first;
if (X!=Y) path.push_back(X);
}
while (X!=Y){
ans = max(ans,p[X].second);
ans = max(ans,p[Y].second);
X = p[X].first;
Y = p[Y].first;
path.push_back(X);
path1.push_back(Y);
}
for (int i = 1;i<path.size();i++){
for (int j = 0;j<n1[path[i]].size();j++){
if (n1[path[i]][j].first==path[i-1] or (i!=path.size()-1 and n1[path[i]][j].first==path[i+1]) or (i==path.size()-1 and n1[path[i]][j].first==path1[path1.size()-1])){
continue;
}
ans1 = min(ans1,n1[path[i]][j].second);
}
}
for (int i = 1;i<path1.size();i++){
for (int j = 0;j<n1[path1[i]].size();j++){
if (n1[path1[i]][j].first==path1[i-1] or (i!=path1.size()-1 and n1[path1[i]][j].first==path1[i+1]) or (i==path1.size()-1 and n1[path[i]][j].first==path[path.size()-1])){
continue;
}
ans1 = min(ans1,n1[path1[i]][j].second);
}
}
if (ans1==1e9+1) return -1;
return max(ans,ans1);
}