| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 552541 | StrawHatWess | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define F first
#define S second
#define PB push_back
const int maxn = 2e5 + 2;
const int maxk = 1000001;
const int INF=2e9;
void IO() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
//-----------------------------------
int n, k, sz[maxn], done[maxn], ans[maxk], tot=maxk;
vector<pi> adj[maxn];
void getSize(int u, int pre) {
sz[u] = 1;
for (auto it : adj[u]) {
int v=it.F, w=it.S;
if (!done[v] && v != pre) {
getSize(v, u);
sz[u] += sz[v];
}
}
}
int centroid(int u, int pre, int tot) {
for (auto it : adj[u]) {
int v=it.F, w=it.S;
if (v != pre && !done[v] && sz[v]*2 >= tot)
return centroid(v, u, tot);
}
return u;
}
void getPaths(int u, int pre, int d, int e, vector<pi> &tmp;) {
if (d <= k) {
tot = min(tot, ans[k-d] + e);
tmp.PB({d, e});
}
for (auto it : adj[u]) {
int v=it.F, w=it.S;
if (!done[v] && v!=pre)
getPaths(v, u, d+w, e+1, tmp);
}
}
void solve(int u) {
getSize(u, -1);
u = centroid(u, -1, sz[u]);
done[u] = 1;
vi vec;
for (auto it : adj[u]) {
int v=it.F, w=it.S;
if (!done[v]){
vector<pi> tmp;
getPaths(v, u, w, 1, tmp);
for (auto it : tmp){
int d=it.F, e=it.S;
ans[d] = min(ans[d], e);
vec.PB(d);
}
}
}
for(int x: vec) ans[x]=INF;
ans[0]=0;
for (auto it : adj[u]) {
int v=it.F, w=it.S;
if (!done[v]) solve(v);
}
}
/*int main() {
IO();
cin >> n >> k;
for (int u,v,w,i=0; i<n-1; i++) {
cin >> u >> v >> w;
adj[u].PB({v, w}); adj[v].PB({u, w});
}
solve(1);
cout << (tot == maxk ? -1 : tot) << endl;
}
*/
int best_path(int n, int k, int H[][2], int L[]){
::n=n; ::k=k;
for (int u,v,w,i=0; i<n-1; i++) {
u = H[i][0], v=H[i][1], w=L[i];
adj[u].PB({v, w}); adj[v].PB({u, w});
}
solve(0);
return (tot == maxk ? -1 : tot);
}