| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 351098 | Kenzo_1114 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
const int MAXD = 1000010;
int n, k, n_cur, sub[MAXN], best[MAXD], ans = MAXD;
vector<int> graph[MAXN], cost[MAXN];
bool marc[MAXN];
void find_sub(int v, int p)
{
sub[v] = 1;
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
if(u == p || marc[u]) continue;
find_sub(u, v), sub[v] += sub[u];
}
}
int find_centroid(int v, int p)
{
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
if(u == p || marc[u]) continue;
if(2 * sub[u] >= n_cur) return find_centroid(u, v);
}
return v;
}
void dfs(int v, int p, int dist, int depth, bool flag)
{
if(k < dist) return;
if(flag)
{
if(best[dist] == 0) best[dist] = depth;
else best[dist] = min(best[dist], depth);
}
else best[depth] = 0;
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
int c = cost[v][i];
if(u != p && !marc[u]) dfs(u, v, dist + c, depth + 1, flag);
}
}
void dfs2(int v, int p, int dist, int depth)
{
if(k < dist) return;
if(best[k - dist]) ans = min(ans, best[k - dist] + depth);
if(dist == k) ans = min(ans, depth);
for(int i = 0; i < (int) graph[v].size(); i++)
{
int u = graph[v][i];
int c = graph[v][i];
if(u != p && !marc[u]) dfs2(u, v, dist + c, depth + 1);
}
}
void decompose(int v, int p)
{
find_sub(v, p);
n_cur = sub[v];
int c = find_centroid(v, p);
// printf("c = %d\n", c);
marc[c] = true;
for(int i = 0; i < (int) graph[c].size(); i++)
{
int u = graph[c][i];
if(u == p || marc[u]) continue;
dfs2(u, c, cost[c][i], 1);
dfs(u, c, cost[c][i], 1, true);
}
dfs(c, c, 0, 0, false);
for(int i = 0; i < (int) graph[c].size(); i++)
{
int u = graph[c][i];
if(!marc[u]) decompose(u, c);
}
}
int best_path(int N, int K, int h[][MAXN], int l[])
{
n = N, k = K;
for(int i = 0; i < n - 1; i++)
{
int u = h[0][i] + 1;
int v = h[1][i] + 1;
int w = l[i];
graph[u].push_back(v);
graph[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
}
decompose(1, 1);
return (ans == MAXD) ? -1 : ans;
}