| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 599067 | acatmeowmeow | 경주 (Race) (IOI11_race) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int NMAX = 2e5 + 5, LG = 20;
// binary lifting
vector<pair<int, int>> adj1[NMAX];
int tin[NMAX], tout[NMAX], timer = 0, anc[NMAX][LG + 5], d[NMAX], h[NMAX];
void dfs1(int u, int e) {
if (u) anc[u][0] = e;
for (int i = 1; i <= LG; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
for (auto&x : adj1[u]) {
int v = x.first, c = x.second;
if (v == e) continue;
d[v] = d[u] + c, h[v] = h[u] + 1;
dfs1(v, u);
}
}
int lca(int u, int v) {
if (h[u] < h[v]) swap(u, v);
int d = h[u] - h[v];
for (int i = 0; i <= LG; i++) { if (d & (1ll << i)) u = anc[u][i]; }
if(u == v) return u;
for (int i = LG; i >= 0; i--) { if (anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i]; }
return anc[u][0];
}
int path_cost(int u, int v) { return d[u] + d[v] - 2*d[lca(u, v)]; }
int path_edge(int u, int v) { return h[u] + h[v] - 2*h[lca(u, v)]; }
// centroid decomposition
set<int> adj2[NMAX];
int p[NMAX], sz[NMAX];
int dfs2(int u, int e) {
sz[u] = 1;
for (auto&v : adj2[u]) {
if (v == e) continue;
sz[u] += dfs2(v, u);
}
return sz[u];
}
int dfs3(int u, int e, int s) {
for (auto&v : adj2[u]) { if (v != e && sz[v] > s/2) return dfs3(v, u, s); }
return u;
}
void build(int u, int e) {
int s = dfs2(u, e), centroid = dfs3(u, e, s);
p[centroid] = e;
set<int> cur = adj2[centroid];
for (auto&v : cur) {
adj2[centroid].erase(v), adj2[v].erase(centroid);
build(v, centroid);
}
}
// solve the problem
vector<int> adj3[NMAX];
void init(int N) {
for (int i = 0; i < N; i++) {
if (p[i] == -1) continue;
adj3[i].push_back(p[i]), adj3[p[i]].push_back(i);
}
}
map<int, int> mn[NMAX];
int ans = 1e18;
void solve(int u, int e, int K) {
for (int v = u; v != -1; v = p[v]) {
int cost = path_cost(u, v), edge = path_edge(u, v);
if (mn[v].count(K - cost)) {
ans = min(ans, edge + mn[v][K - cost]);
cout << u << ' ' << v << ' ' << edge << ' ' << mn[v][K - cost] << '\n';
}
if (!mn[v].count(cost)) mn[v][cost] = 1e18;
mn[v][cost] = min(mn[v][cost], edge);
}
for (auto&v : adj3[u]) {
if (v == e) continue;
solve(v, u, K);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; i++) {
int u = H[i][0], v = H[i][1], c = L[i];
adj1[u].push_back({v, c}), adj1[v].push_back({u, c});
adj2[u].insert(v), adj2[v].insert(u);
}
dfs1(0, -1);
build(0, -1);
init(N);
solve(0, -1, K);
return ans == 1e18 ? -1 : ans;
}
/*int N, K, H[NMAX][2], L[NMAX];
signed main() {
cin >> N >> K;
for (int i = 0; i < N - 1; i++) cin >> H[i][0] >> H[i][1] >> L[i];
cout << best_path(N, K, H, L) << '\n';
return 0;
}*/