제출 #387923

#제출 시각아이디문제언어결과실행 시간메모리
387923pure_mem경주 (Race) (IOI11_race)C++14
0 / 100
3088 ms4940 KiB
#include "race.h" #include <bits/stdc++.h> #define X first #define Y second #define ll long long #define MP make_pair using namespace std; const int MAXN = 2e5 + 12; int answer, n, k, sz[MAXN], mx[MAXN], block[MAXN]; vector< pair<int, int> > graph[MAXN]; set< pair<ll, int> > stAct; void dfs_sz(int v, int pr){ sz[v] = 1, mx[v] = 0; for(pair<int, int> to: graph[v]){ if(to.X != pr && !block[to.X]){ dfs_sz(to.X, v), sz[v] += sz[to.X]; if(sz[mx[v]] < sz[to.X]) mx[v] = to.X; } } } int get_cent(int v){ int u = v; while(sz[v] < sz[mx[u]] * 2) u = mx[u]; return u; } void dfs_prep(int v, int pr, ll cost, int dist){ if(cost > k) return; auto it = stAct.lower_bound(MP(k - cost + 1, 0)); if(it != stAct.begin() && prev(it)->X + cost == k) answer = min(answer, dist + prev(it)->Y); for(pair<int, int> to: graph[v]){ if(to.X != pr && !block[to.X]) dfs_prep(to.X, v, cost + to.Y, dist + 1); } } void dfs_add(int v, int pr, ll cost, int dist){ if(cost > k) return; auto it = stAct.lower_bound(MP(cost + 1, 0)); if(it != stAct.begin() && prev(it)->X == cost && prev(it)->Y > dist) stAct.erase(prev(it)), stAct.insert(MP(cost, dist)); else if(it == stAct.begin() || prev(it)->X != cost) stAct.insert(MP(cost, dist)); for(pair<int, int> to: graph[v]){ if(to.X != pr && !block[to.X]) dfs_add(to.X, v, cost + to.Y, dist + 1); } } void cent(int v){ dfs_sz(v, v); v = get_cent(v); block[v] = 1; stAct.clear(); stAct.insert(MP(0, 0)); for(pair<int, int> to: graph[v]){ if(!block[to.X]) dfs_prep(to.X, v, to.Y, 1), dfs_add(to.X, v, to.Y, 1); } for(pair<int, int> to: graph[v]){ if(!block[to.X]) cent(to.X); } } int best_path(int N, int K, int H[][2], int L[]) { answer = N + 1, n = N, k = K; for(int i = 0;i < n;i++){ graph[H[i][0] + 1].push_back(MP(H[i][1] + 1, L[i])); graph[H[i][1] + 1].push_back(MP(H[i][0] + 1, L[i])); } cent(1); if(answer == N + 1) answer = -1; return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...