제출 #387903

#제출 시각아이디문제언어결과실행 시간메모리
387903pure_mem경주 (Race) (IOI11_race)C++14
21 / 100
182 ms15776 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 rnd(){ return ((rand() << 15) + rand()); } struct node{ int l = 0, r = 0, pr = 0, tt2 = 0, dval = 0; ll val = 0, tt1 = 0; void init(ll _val, int _dval){ l = r = 0, tt1 = tt2 = 0; val = _val, dval = _dval, pr = rnd(); } }t[MAXN]; int root, tSize; void push(int v){ if(!v || !t[v].tt2) return; int l = t[v].l, r = t[v].r; if(l){ t[l].val += t[v].tt1, t[l].tt1 += t[v].tt1; t[l].dval += t[v].tt2, t[l].tt2 += t[v].tt2; } if(r){ t[r].val += t[v].tt1, t[r].tt1 += t[v].tt1; t[r].dval += t[v].tt2, t[r].tt2 += t[v].tt2; } t[v].tt1 = t[v].tt2 = 0; } void walk(int v){ if(!v) return; push(v); walk(t[v].l); cerr << t[v].val << "\n"; walk(t[v].r); } void split(int v, int &l, int &r, ll val){ push(v); if(!v) return void(l = r = 0); if(val <= t[v].val) split(t[v].l, l, t[v].l, val), r = v; else split(t[v].r, t[v].r, r, val), l = v; } void merge(int &v, int l, int r){ if(!l || !r) return void(v = l ? l: r); if(t[l].pr > t[r].pr){ push(l); merge(t[l].r, t[l].r, r), v = l; } else{ push(r); merge(t[r].l, l, t[r].l), v = r; } } void insert(int &v, int oth){ push(v); if(!v) v = oth; else if(t[v].pr < t[oth].pr){ split(v, t[oth].l, t[oth].r, t[oth].val), v = oth; } else{ if(t[oth].val < t[v].val) insert(t[v].l, oth); else insert(t[v].r, oth); } } int isGood(int v, ll val, int dval){ push(v); if(!v) return 0; if(t[v].val == val){ t[v].dval = min(t[v].dval, dval); return t[v].dval; } else if(val < t[v].val) return isGood(t[v].l, val, dval); else return isGood(t[v].r, val, dval); } int answer, n, k, sz[MAXN]; vector< pair<int, int> > graph[MAXN]; void dfs_sz(int v, int pr){ sz[v] = 1; for(pair<int, int> to: graph[v]){ if(to.X != pr){ dfs_sz(to.X, v); sz[v] += sz[to.X]; } } } void dfs_prep(int v, int pr, ll cost, int dist){ if(cost > k) return; int tmp = isGood(root, k - cost, n + 12); if(tmp) answer = min(answer, tmp + dist); for(pair<int, int> to: graph[v]){ if(to.X == pr) continue; 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; if(!isGood(root, cost, dist)){ t[++tSize].init(cost, dist); insert(root, tSize); } for(pair<int, int> to: graph[v]){ if(to.X == pr) continue; dfs_add(to.X, v, cost + to.Y, dist + 1); } } void dfs(int v, int pr, bool keep){ int mx = 0, cost = 0; for(pair<int, int> to: graph[v]){ if(to.X != pr && sz[mx] < sz[to.X]) mx = to.X, cost = to.Y; } for(pair<int, int> to: graph[v]){ if(to.X != pr && mx != to.X) dfs(to.X, v, 0); } if(mx){ dfs(mx, v, 1); if(root) t[root].val += cost, t[root].dval += 1, t[root].tt1 += cost, t[root].tt2 += 1; int tmp = isGood(root, k, n + 12); if(tmp) answer = min(answer, tmp); } t[++tSize].init(0, 1); insert(root, tSize); for(pair<int, int> to: graph[v]){ if(to.X != pr && mx != to.X) dfs_prep(to.X, v, to.Y, 1), dfs_add(to.X, v, to.Y, 2); } if(!keep) root = 0, tSize = 0; } 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])); } dfs_sz(1, 1); dfs(1, 1, 0); if(answer == N + 1) answer = -1; else 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...