제출 #281773

#제출 시각아이디문제언어결과실행 시간메모리
281773PKhing경주 (Race) (IOI11_race)C++14
0 / 100
146 ms262148 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<int,int> #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<int> sz[200005]; queue<ii> len[200005]; set<ii> edge[200005]; 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,int l,int cnt,int cen){ len[cen].p(l,cnt); for(auto v:edge[u]){ if(v.f!=p){ setlen(v.f,u,l+v.s,cnt+1,cen); } } } int decomp(int u,int p){ dfs(u,-1); if(p!=-1)sz[p].p(size[u]); int x = centroid(u,-1,size[u]); for(auto v:edge[x]){ setlen(v.f,x,v.s,1,x); edge[v.f].erase(mp(x,v.s)); decomp(v.f,x); } edge[x].clear(); return x; } int ans = INF; void findpath(int u,int k){ //db(u); int cnt = 0; set<ii> f,tmp; while(sz[u].size()>0){ //printf("%d ",len[u].front()); tmp.p(len[u].front()); auto x = f.upper_bound(mp(k-len[u].front().f,-1)); if(x->f == k-len[u].front().f)ans = min(ans,x->s+len[u].front().s); len[u].pop(); cnt++; if(cnt==sz[u].front()){ for(auto i:tmp){ f.insert(i); } tmp.clear(); cnt = 0; sz[u].pop(); // printf("\nchange "); } } //cout<<endl<<endl; } int best_path(int N, int K, int H[][2], int L[]) { 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); FOR(i,N){ findpath(i,K); } 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...