| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 151421 | flashmt | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 200200, oo = 1 << 21;
int n, k, h[N][2], l[N], height[N], pos[N], deltaVal[N], st[N], last, curChild[N], par[N];
long long deltaID[N];
vector<pair<int, int>> a[N];
vector<int> order;
map<long long, int> m[N];
int ans = oo;
int unionMap(int u, int v, int c)
{
int res = oo;
long long offsetID = c + deltaID[u] + deltaID[v];
int offsetVal = 1 + deltaVal[u] + deltaVal[v];
for (auto it : m[v])
if (m[u].count(k - it.first - offsetID))
res = min(res, it.second + m[u][k - it.first - offsetID] + offsetVal);
offsetID = c + deltaID[v] - deltaID[u];
offsetVal = 1 + deltaVal[v] - deltaVal[u];
for (auto it : m[v])
if (!m[u].count(it.first + offsetID) || m[u][it.first + offsetID] > it.second + offsetVal)
m[u][it.first + offsetID] = it.second + offsetVal;
m[v].clear();
return res;
}
int calc(int x)
{
int mxSize = 0, res = oo, tmp;
pos[x] = x;
for (auto u : a[x])
{
int y = u.first;
if (y == par[x]) continue;
int sizeY = m[pos[y]].size();
if (sizeY > mxSize)
{
mxSize = sizeY;
pos[x] = pos[y];
tmp = u.second;
}
}
if (pos[x] == x)
{
m[x][0] = 0;
return res;
}
int u = pos[x];
deltaID[u] += tmp;
deltaVal[u]++;
if (m[u].count(k - deltaID[u]))
res = min(res, m[u][k - deltaID[u]] + deltaVal[u]);
if (!m[u].count(-deltaID[u]) || m[u][-deltaID[u]] > -deltaVal[u])
m[u][-deltaID[u]] = -deltaVal[u];
for (auto u : a[x])
{
int y = u.first;
if (y == par[x] || pos[x] == pos[y]) continue;
res = min(res, unionMap(pos[x], pos[y], u.second));
}
return res;
}
void dfs(int x)
{
for (auto u : a[x])
{
int y = u.first;
if (y == par[x])
continue;
par[y] = x;
dfs(y);
}
ans = min(ans, calc(x));
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int x, y, z;
cin >> n >> k;
for (int i = 1; i < n; i++)
{
cin >> x >> y >> z;
a[x].push_back({y, z});
a[y].push_back({x, z});
}
par[0] = -1;
dfs(0);
cout << (ans != oo ? ans : -1) << endl;
}