| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 938541 | duckindog | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#include "race.h"
#endif
const int N = 200'000 + 10;
vector<pair<int, int>> ad[N];
namespace sub1 {
int d[N];
int solve(int n, int k, vector<int>& l) {
for (int i = 1; i <= n; ++i) d[i] = d[i - 1] + l[i - 1];
int answer = 1e7;
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
if (d[j] - d[i - 1] == k) answer = min(answer, j - i + 1);
return answer;
}
}
namespace sub2 {
int d[N], dep[N];
int f[N][10], st[N], ed[N], it;
void dfs(int u, int pre = 0) {
st[u] = ++it;
for (int i = 1; i <= 9; ++i)
f[u][i] = f[f[u][i - 1]][i - 1];
for (const auto& [v, w] : ad[u]) {
if (v == pre) continue;
d[v] = d[u] + w;
dep[v] = dep[u] + 1;
f[v][0] = u;
dfs(v, u);
}
ed[u] = it;
}
bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int lca(int u, int v) {
if (anc(u, v)) return u;
if (anc(v, u)) return v;
for (int i = 9; i >= 0; --i)
if (!anc(f[u][i], v)) u = f[u][i];
return f[u][0];
}
int solve(int n, int k) {
dfs(0);
int answer = 1e7;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int l = lca(i, j);
int distant = d[i] + d[j] - 2 * d[l], cnt = dep[i] + dep[j] - 2 * dep[l];
if (distant == k) answer = min(answer, cnt);
}
}
return answer;
}
}
int best_path(int n, int k, vector<vector<int>>& h, vector<int>& l) {
int sub = 1;
for (int i = 0; i < n - 1; ++i) {
int u = h[i][0], v = h[i][1], w = l[i];
if (u > v) swap(u, v);
ad[u].push_back({v, w});
ad[v].push_back({u, w});
if (u != i || v != i + 1) sub = 2;
}
sub = (n <= 1'000 ? 2 : k <= 100 ? 3 : 4);
if (sub == 1) return sub1::solve(n, k, l);
if (sub == 2) return sub2::solve(n, k);
return -1;
}
#ifdef LOCAL
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
vector<vector<int>> h(n, vector<int>(2));
vector<int> l(n);
for (int i = 0; i < n - 1; ++i) cin >> h[i][0] >> h[i][1] >> l[i];
cout << best_path(n, k, h, l);
}
#endif