제출 #281859

#제출 시각아이디문제언어결과실행 시간메모리
281859PKhing경주 (Race) (IOI11_race)C++14
0 / 100
8 ms9728 KiB
#include "race.h" #include<bits/stdc++.h> #define FOR(i,a) for(int i=0;i<a;i++) #define FOR1(i,a) for(int i=1;i<=a;i++) #define db(a) printf("<%d> ",a) #define f first #define s second #define all(x) x.begin(),x.end() #define mp make_pair #define pb emplace_back #define p emplace #define ii pair<long long,long long> #define ll long long #define rf() freopen("_working/input.in","r",stdin) #define pf() freopen("_working/output.out","w+",stdout) using namespace std; const int INF=1e9; int size[200005]; queue<ii> len; set<ii> edge[200005]; ll ans = INF; int centroid(int u,int p,int n){ for(auto v:edge[u]){ if(v.f!=p && size[v.f]>n/2)return centroid(v.f,u,n); } return u; } void dfs(int u,int p){ size[u]=1; for(auto v:edge[u]){ if(v.f!=p){ dfs(v.f,u); size[u]+=size[v.f]; } } } void setlen(int u,int p,ll l,int cnt){ len.p(l,cnt); for(auto v:edge[u]){ if(v.f!=p){ setlen(v.f,u,l+(ll)v.s,cnt+1); } } } ll k; void decomp(int u,int p){ set<ii> f,tmp; dfs(u,-1); int x = centroid(u,-1,size[u]); for(auto v:edge[x]){ setlen(v.f,x,v.s,1); while(!len.empty()){ tmp.p(len.front()); auto x = f.upper_bound(mp(k-len.front().f,-1)); if(x->f == k-len.front().f)ans = min(ans,x->s+len.front().s); len.pop(); } for(auto i:tmp){ f.insert(i); } tmp.clear(); } for(auto v:edge[x]){ edge[v.f].erase(mp(x,v.s)); decomp(v.f,x); } edge[x].clear(); } int best_path(int N, int K, int H[][2], int L[]) { k=K; for(int i=0;i<N-1;i++){ edge[H[i][0]].p(H[i][1],L[i]); edge[H[i][1]].p(H[i][0],L[i]); } decomp(0,-1); return ans==1e9?-1:ans; } // int H[200005][2],L[200005]; // int N,K; // int main(){ // cin>>N>>K; // FOR(i,N-1){ // scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]); // } // printf("%d",best_path(N,K,H,L)); // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...