| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1165633 | SmuggingSpun | Swapping Cities (APIO20_swap) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "swap.h"
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 1e5 + 5;
const int INF = 1e9;
bool is_sub2;
int n, m, u[lim << 1], v[lim << 1], w[lim << 1];
vector<int>g[lim];
namespace sub2{
int third;
void init(){
vector<int>p(n - 1);
iota(p.begin(), p.end(), 1);
sort(p.begin(), p.end(), [&] (int i, int j){
return w[g[i][0]] < w[g[j][0]];
});
if(n > 3){
third = p[2];
}
}
}
namespace sub5{
int h[lim], up[lim][17], mx[lim][17], mi[lim][17];
vector<pair<int, int>>opt[lim];
void dfs_1(int s, int p = -1){
for(int& i : g[s]){
int d = u[i] ^ v[i] ^ s;
if(d != p){
h[d] = h[up[d][0] = s] + 1;
mx[d][0] = w[i];
for(int i = 1; i < 17; i++){
up[d][i] = up[up[d][i - 1]][i - 1];
mx[d][i] = max(mx[d][i - 1], mx[up[d][i - 1]][i - 1]);
}
dfs_1(d, s);
opt[s].emplace_back(d, w[i]);
}
}
}
void dfs_2(int s, int p = -1){
sort(opt[s].begin(), opt[s].end());
while(opt[s].size() < 3){
opt[s].emplace_back(-1, INF);
}
for(int& i : g[s]){
int d = u[i] ^ v[i] ^ s;
if(d != p){
for(int j = 0; true; j++){
if(opt[s][j].first != d){
mi[d][0] = opt[s][j].second;
for(int k = 1; k < 17; k++){
mi[d][k] = min(mi[d][k - 1], mi[up[d][k - 1]][k - 1]);
}
dfs_2(d, s);
break;
}
}
}
}
}
int lca(int u, int v){
if(h[u] < h[v]){
swap(u, v);
}
for(int i = 0, k = h[u] - h[v]; i < 17; i++){
if(1 << i & k){
u = up[u][i];
}
}
if(u == v){
return u;
}
for(int i = 16; i > -1; i--){
if(up[u][i] != up[v][i]){
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
int query(int u, int v){
int root = lca(u, v), ans_max = 0, ans_min = INF, ut = u, vt = v;
for(int i = 0, uk = u, vk = v, ku = h[u] - h[root], kv = h[v] - h[root], tu = h[u] - h[root] - 1, tv = h[v] - h[root] - 1; i < 17; i++){
if(1 << i & ku){
maximize(ans_max, mx[uk][i]);
uk = up[uk][i];
}
if(1 << i & kv){
maximize(ans_max, mx[vk][i]);
vk = up[vk][i];
}
if(tu > 0 && (1 << i & tu)){
minimize(ans_min, mi[ut][i]);
ut = up[ut][i];
}
if(tv > 0 && (1 << i & tv)){
minimize(ans_min, mi[vt][i]);
vt = up[vt][i];
}
}
for(auto& [vertex, val] : opt[root]){
if(vertex != ut && vertex != vt){
minimize(ans_min, val);
break;
}
}
return max(ans_max, ans_min);
}
void init(){
memset(up, 0, sizeof(up));
memset(mx, 0, sizeof(mx));
memset(mi, 0x3f, sizeof(mi));
dfs_1(0);
dfs_2(0);
}
}
void init(int N, int M, vector<int>U, vector<int>V, vector<int>W){
n = N;
m = M;
for(int i = 0; i < m; i++){
g[u[i] = U[i]].emplace_back(i);
g[v[i] = V[i]].emplace_back(i);
w[i] = W[i];
}
if(is_sub2 = (*max_element(u, u + m) == 0 && m == n - 1)){
sub2::init();
return;
}
if(m == n - 1){
sub5::init();
return;
}
}
int getMinimumFuelCapacity(int x, int y){
if(is_sub2){
if(x == 0){
return n < 4 ? -1 : max(w[g[y][0]], w[g[sub2::third][0]]);
}
return n < 4 ? -1 : max({w[g[x][0]], w[g[y][0]], w[g[sub2::third][0]]});
}
if(m == n - 1){
return sub5::query(u, v);
}
}