제출 #563434

#제출 시각아이디문제언어결과실행 시간메모리
563434hibiki경주 (Race) (IOI11_race)C++11
43 / 100
3054 ms33260 KiB
#include "race.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define f first #define s second // global int ans = 1e9, n, kk; vector<pair<int,long long> > v[200005]; // centroid int sz[200005]; bool visited[200005]; // query & update int has[1000005]; void query(int nw,int fa,int dep,long long total) { if(total > kk) return ; if(has[kk - total] != 1e9) ans = min(ans, dep + has[kk - total]); for(auto go: v[nw]) if(go.f != fa && !visited[go.f]) query(go.f, nw, dep + 1, total + go.s); } void update(int nw,int fa,int dep, long long total) { if(total > kk) return ; has[total] = min(has[total], dep); for(auto go: v[nw]) if(go.f != fa && !visited[go.f]) update(go.f, nw, dep + 1, total + go.s); } int re_size(int nw,int fa) { sz[nw] = 1; for(auto go: v[nw]) if(go.f != fa && !visited[go.f]) sz[nw] += re_size(go.f,nw); return sz[nw]; } int fi_cen(int nw,int fa,int sum) { for(auto go: v[nw]) if(go.f != fa && !visited[go.f] && sz[go.f] > sum/2) return fi_cen(go.f,nw,sum); return nw; } void centroid_decomp(int nw) { int cen = fi_cen(nw, -1, re_size(nw, -1)); visited[cen] = true; has[0] = 0; for(int i = 1; i <= kk; i++) has[i] = 1e9; for(auto go: v[cen]) { if(!visited[go.f]) { query(go.f, cen, 1, go.s); update(go.f, cen, 1, go.s); } } for(auto go: v[cen]) if(!visited[go.f]) centroid_decomp(go.f); } int best_path(int N, int K, int H[][2], int L[]) { n = N, kk = K; for(int i = 0; i < n - 1; i++) { v[H[i][0]].pb({H[i][1], L[i]}); v[H[i][1]].pb({H[i][0], L[i]}); } centroid_decomp(0); if(ans == 1e9) return -1; return ans; } // int a,b; // int send[200005][2],send2[200005]; // int main() // { // scanf("%d %d",&a,&b); // for(int i = 0; i < a - 1; i++) // scanf("%d %d %d",&send[i][0],&send[i][1],&send2[i]); // printf("%d",best_path(a, b, send, send2)); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...