제출 #1078132

#제출 시각아이디문제언어결과실행 시간메모리
1078132Malix경주 (Race) (IOI11_race)C++14
100 / 100
1399 ms115008 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define REP(a,b,c) for(int a=b;a<c;a++) #define PB push_back #define F first #define S second #define LSOne(s) ((s)&(-s)) typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; int inf=1000000010; int n,k,sv=0,ev=0,m; vector<pii> a; vi s,st,en,depth,length,vis; vii p,b,c; int ans=inf; void dfs(int x){ st[x]=sv++; for(auto u:a[x])if(p[x][0]!=u.F){ p[u.F][0]=x; depth[u.F]=depth[x]+1; length[u.F]=length[x]+u.S; dfs(u.F); s[x]+=s[u.F]; } en[x]=ev++; } int centroid(int x){ for(auto u:a[x])if(!vis[u.F]&&s[u.F]>s[x]/2){ s[x]-=s[u.F]; s[u.F]+=s[x]; return centroid(u.F); } return x; } void decompose(int x){ for(auto u:a[x])if(!vis[u.F]){ int y=centroid(u.F); b[x].PB(y); vis[y]=1; decompose(y); } } bool ances(int x,int y){ if(y==-1)return 1; if(st[x]>=st[y]&&en[x]<=en[y])return 1; return 0; } pi dist(int x,int y){ if(ances(x,y)||ances(y,x)) return {abs(depth[x]-depth[y]),abs(length[x]-length[y])}; int z=y; for(int i=m-1;i>=0;i--)if(!ances(x,p[y][i]))y=p[y][i]; y=p[y][0]; return {depth[x]+depth[z]-2*depth[y],length[x]+length[z]-2*length[y]}; } void solve(int x){ unordered_map<int,int> mp; c[x].PB(x); for(auto u:b[x]){ solve(u); unordered_map<int,int> tmp; for(auto v:c[u]){ pi r=dist(v,x); if(r.S>k)continue; if(r.S==k){ ans=min(ans,r.F); continue; } if(tmp[r.S]==0)tmp[r.S]=r.F; else tmp[r.S]=min(tmp[r.S],r.F); if(mp[k-r.S]!=0)ans=min(ans,mp[k-r.S]+r.F); } for(auto v:tmp){ if(mp[v.F]==0)mp[v.F]=v.S; else mp[v.F]=min(mp[v.F],v.S); } for(auto u:c[u])c[x].PB(u); } } int best_path(int N, int K, int H[][2], int L[]) { n=N;k=K; m=log2(n)+2; a.resize(n); REP(i,0,n-1){ a[H[i][0]].PB({H[i][1],L[i]}); a[H[i][1]].PB({H[i][0],L[i]}); } p.resize(n,vi(m,-1));s.resize(n,1);st.resize(n);en.resize(n); depth.resize(n,0);length.resize(n,0);vis.resize(n,0); vis.resize(n,0);b.resize(n);c.resize(n); dfs(0); REP(j,1,m)REP(i,0,n)if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1]; int x=centroid(0); vis[x]=1; decompose(x); solve(x); if(ans==inf)return -1; return 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...