제출 #238699

#제출 시각아이디문제언어결과실행 시간메모리
238699T0p_경주 (Race) (IOI11_race)C++14
21 / 100
3092 ms215672 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define N 200002 #define pb push_back struct EDGE { int node, weight; }; int ans = 1e9, K; int lv[N], jmp[2][20][N], sz[N]; bool visit[N]; map<int, int> mp[N]; vector<EDGE> g[N]; void dfs(int u, int l) { lv[u] = l; for(auto x : g[u]) { if(lv[x.node]) continue ; dfs(x.node, l+1); jmp[0][0][x.node] = u; jmp[1][0][x.node] = x.weight; } } int get_sz(int u, int p) { sz[u] = 1; for(auto x : g[u]) { if(visit[x.node] || x.node == p) continue ; sz[u] += get_sz(x.node, u); } return sz[u]; } int get_centroid(int u, int p, int n) { bool ch = (n - sz[u] <= n/2) ? true : false; int nn = 0, nf = 0; for(auto x : g[u]) { if(visit[x.node] || x.node == p) continue ; if(sz[x.node] > n/2) { ch = false; if(sz[x.node] > nf) { nn = x.node; nf = sz[x.node]; } } } return (ch) ? u : get_centroid(nn, u, n); } pair<int, int> finddis(int u, int v) { int r1 = 0, r2 = 0; if(lv[u] < lv[v]) swap(u, v); for(int i=19 ; i>=0 ; i--) if(lv[jmp[0][i][u]] >= lv[v]) { r1 += (1<<i); r2 += jmp[1][i][u]; u = jmp[0][i][u]; } if(u == v) return {r1, r2}; for(int i=19 ; i>=0 ; i--) if(jmp[0][i][u] != jmp[0][i][v]) { r1 += (1<<(i+1)); r2 += jmp[1][i][u] + jmp[1][i][v]; u = jmp[0][i][u], v = jmp[0][i][v]; } return {r1+2, r2+jmp[1][0][u]+jmp[1][0][v]}; } void compute(int u, int p, int r) { pair<int, int> dis = finddis(u, r); if(dis.second == K) ans = min(ans, dis.first); else if(mp[r].count(K - dis.second)) ans = min(ans, mp[r][K - dis.second] + dis.first); for(auto x : g[u]) { if(visit[x.node] || x.node == p) continue ; compute(x.node, u, r); } } void update(int u, int p, int r) { pair<int, int> dis = finddis(u, r); if(mp[r].count(dis.second)) mp[r][dis.second] = min(mp[r][dis.second], dis.first); else mp[r][dis.second] = dis.first; for(auto x : g[u]) { if(visit[x.node] || x.node == p) continue ; update(x.node, u, r); } } void build(int u, int p) { int c = get_centroid(u, p, get_sz(u, p)); visit[c] = true; for(auto x : g[c]) { if(visit[x.node]) continue ; compute(x.node, c, c); update(x.node, c, c); } for(auto x : g[c]) { if(visit[x.node]) continue ; build(x.node, c); } } int best_path(int n, int k, int h[][2], int l[]) { K = k; for(int i=0 ; i<n-1 ; i++) { g[h[i][0]+1].pb({h[i][1]+1, l[i]}); g[h[i][1]+1].pb({h[i][0]+1, l[i]}); } dfs(1, 1); for(int i=1 ; i<20 ; i++) for(int j=1 ; j<=n ; j++) { jmp[0][i][j] = jmp[0][i-1][jmp[0][i-1][j]]; jmp[1][i][j] = jmp[1][i-1][j] + jmp[1][i-1][jmp[0][i-1][j]]; } build(1, 0); return (ans == 1e9) ? -1 : ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...