| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 298027 | miss_robot | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "grader.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
using namespace std;
int INF = numeric_limits<int>::max()/4, best[1000001];
void dfs(int u, int p, vector<int>& st, vector<int>& active, vector< vector<pair<int, int> > >& g){
st[u] = 1;
for(auto &t : g[u]){
if(!active[t.first] || t.first == p) continue;
dfs(t.first, u, st, active, g);
st[u] += st[t.first];
}
}
int fnd(int u, int p, int n, vector<int>& st, vector<int>& active, vector< vector<pair<int, int> > >& g){
for(auto &t : g[u]){
if(!active[t.first] || t.first == p) continue;
if(st[t.first] > n/2) return fnd(t.first, u, n, st, active, g);
}
return u;
}
void sum(int u, int p, int d, int num, vector< pair<int, int> >& temp, vector<int>& active, vector< vector< pair<int, int> > >& g){
temp.push_back({num++, d});
for(auto& t : g[u]){
if(t.first == p || !active[t.first]) continue;
sum(t.first, u, d+t.second, num, temp, active, g);
}
}
void solve(int u, int k, vector<int>& st, vector<int>& active, vector< vector< pair<int, int> > >& g, int& b){
dfs(u, u, st, active, g);
u = fnd(u, u, st[u], st, active, g);
vector<int> ers;
vector< pair<int, int> > temp;
for(auto &t : g[u]){
if(!active[t.first]) continue;
temp.clear();
sum(t.first, u, t.second, 1, temp, active, g);
for(auto &q : temp){
if(q.second > k) continue;
else b = min(b, q.first + best[k-q.second]);
}
for(auto &q : temp) if(q.second <= k) best[q.second] = min(best[q.second], q.first), ers.push_back(q.second);
}
for(int &x : ers) best[x] = INF;
active[u] = 0;
for(int i = 0; i < (int)g[u].size(); i++)
if(active[g[u][i].first] && st[g[u][i].first] > 1)
solve(g[u][i].first, k, st, active, g, b);
}
signed best_path(signed N, signed K, signed H[][2], signed L[]){
int n = N, k = K, b = INF, u, v, w;
vector< vector< pair<int, int> > > g(n);
for(int i = 1; i < n; i++){
u = H[i-1][0], v = H[i-1][1], w = L[i-1];
g[u].push_back({v, w}), g[v].push_back({u, w});
}
for(int i = 1; i <= k; i++) best[i] = INF;
vector<int> active(n, 1), st(n);
solve(0, k, st, active, g, b);
return (b==INF?-1:b);
}