| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1228533 | uwubigbadboy | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "race.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define ll long long int
const int N = 2e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;
vector<int> sz(N, 1);
map<ll, pair<pair<int, int>, pair<int, int>>> mp;
vector<vector<pair<int, int>>> g(N, vector<pair<int, int>> ());
vector<vector<int>*> vec(N), vec1(N);
vector<int> dep(N, 1);
vector<vector<int>> up(N, vector<int> (20, -1));
vector<ll> sm(N);
void dfs(int u, int p) {
up[u][0] = p;
for (int i = 1; i <= 20; i++) {
if (up[u][i - 1] != -1) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
}
for (auto v: g[u])
if (v.first != p) {
dep[v.first] = dep[u] + 1;
sm[v.first] = sm[u] + v.second;
dfs(v.first, u);
sz[u] += sz[v.first];
}
}
bool are_parent(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
int del = dep[v] - dep[u];
for (int msk = 0; msk <= 20; msk++) {
if (del & (1 << msk)) {
v = up[v][msk];
}
}
return (u == v);
}
int ans = INF, kkk;
void dfs1(int u, int p, bool keep) {
int sz_max = 0, bg = -1;
for (auto v: g[u]) {
if (v.first != p) {
if (sz[v.first] > sz_max) {
sz_max = sz[v.first];
bg = v.first;
}
}
}
for (auto v: g[u]) {
if (v.first != p && v.first != bg) {
dfs1(v.first, u, 0);
}
}
if (bg != -1) {
dfs1(bg, u, 1);
vec[u] = vec[bg];
} else vec[u] = new vector<int> ();
vec[u] -> push_back(u);
for (auto v: g[u]) {
if (v.first != p && v.first != bg) {
for (auto i: *vec[v.first]) {
if (mp[sm[i]].first.first > dep[i] || mp[sm[i]].first.second == 0) {
swap(mp[sm[i]].first, mp[sm[i]].second);
mp[sm[i]].first = {dep[i], i};
} else if (mp[sm[i]].second.first > dep[i] || mp[sm[i]].second.second == 0) {
mp[sm[i]].second = {dep[i], i};
}
}
}
}
if (mp[sm[u] + kkk].first.second != 0)
ans = min(ans, mp[sm[u] + kkk].first.first - dep[u]);
for (auto v: g[u]) {
if (v.first != p && v.first != bg) {
for (auto i: *vec[v.first]) {
int ss = sm[i] - sm[u];
int other = (kkk - ss) + sm[u];
if (mp[other].first.second != 0 && !are_parent(mp[other].first.second, i)) {
ans = min(ans, (dep[i] - dep[u]) + (dep[mp[other].first.second] - dep[u]));
}
if (mp[other].second.second != 0 && !are_parent(mp[other].second.second, i)) {
ans = min(ans, (dep[i] - dep[u]) + (dep[mp[other].second.second] - dep[u]));
}
}
}
}
if (mp[sm[u]].first.first > dep[u] || mp[sm[u]].first.second == 0) {
swap(mp[sm[u]].first, mp[sm[u]].second);
mp[sm[u]].first = {dep[u], u};
} else if (mp[sm[u]].second.first > dep[u] || mp[sm[u]].second.second == 0) {
mp[sm[u]].second = {dep[u], u};
}
if (keep == 0)
for (auto i: *vec[u]) {
mp[sm[i]] = {{0, 0}, {0, 0}};
}
}
int best_path(int n, int k, vector<vector<int>> h, vector<int> l) {
kkk = k;
ans = INF;
fill(sz.begin(), sz.end(), 1);
fill(dep.begin(), dep.end(), 1);
fill(sm.begin(), sm.end(), 0ll);
for (int i = 0; i < N; i++)
fill(up[i].begin(), up[i].end(), -1);
vec = vec1;
mp = {};
for (int i = 1; i <= n; i++)
g[i].clear();
for (int i = 0; i < (n - 1); i++) {
h[i][0]++, h[i][1]++;
g[h[i][0]].push_back({h[i][1], l[i]});
g[h[i][1]].push_back({h[i][0], l[i]});
}
dfs(1, -1);
dfs1(1, -1, 0);
if (ans == INF) ans = -1;
return ans;
}
// int32_t main(int32_t argc, char *argv[]) {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int T = 1;
// // cin >> T;
// while (T--) {
// int n, k;
// cin >> n >> k;
// vector<vector<int>> h(n - 1, vector<int> (2));
// vector<int> l(n);
// for (int i = 0; i < n - 1; i++)
// cin >> h[i][0] >> h[i][1];
// for (int i = 0; i < n - 1; i++)
// cin >> l[i];
// cout << best_path(n, k, h, l) << '\n';
// }
// return 0;
// }