제출 #797938

#제출 시각아이디문제언어결과실행 시간메모리
797938Khizri경주 (Race) (IOI11_race)C++17
21 / 100
3059 ms10352 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define F first #define S second #define INF 1e18 #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pii pair<int,int> #define pll pair<ll,ll> #define OK cout<<"Ok"<<endl; #define MOD (ll)(1e9+7) const int mxn=2e5+5; int n,k,par[mxn],sub[mxn],color[mxn],sz,first,ans=1e9; map<int,int>global,local; vector<pii>vt[mxn]; void calc(int u,int p){ sz++; sub[u]=1; for(pii pp:vt[u]){ int v=pp.F; if(v!=p&&!color[v]){ calc(v,u); sub[u]+=sub[v]; } } } int find_centroid(int u,int p){ for(pii pp:vt[u]){ int v=pp.F; if(v==p) continue; if(sub[v]*2>sz&&!color[v]){ return find_centroid(v,u); } } return u; } void dfs(int u,int p,ll dis,int dep){ if(dis==k) ans=min(ans,dep); if(dep>0&&dis<=k){ if(global[k-dis]!=0){ ans=min(ans,dep+global[k-dis]); } if(local[dis]==0){ local[dis]=dep; } else{ local[dis]=min(local[dis],dep); } } for(pii pp:vt[u]){ int v=pp.F,len=pp.S; if(dep==0) local.clear(); if(v!=p){ dfs(v,u,dis+len,dep+1); if(dep==0){ for(auto it=local.begin();it!=local.end();it++){ int x=it->F; int y=it->S; if(global[x]==0){ global[x]=y; } else{ global[x]=min(global[x],y); } } } } } } int best_path(int N, int K, int H[][2], int L[]) { n=N,k=K; for(int i=0;i<n-1;i++){ int u=H[i][0]+1,v=H[i][1]+1; vt[u].pb({v,L[i]}); vt[v].pb({u,L[i]}); if(L[i]==k) return 1; } for(int id=1;id<=20;id++){ for(int i=1;i<=n;i++){ if(!color[i]){ sz=0; calc(i,-1); int node=find_centroid(i,-1); color[node]=1; global.clear(); local.clear(); dfs(node,-1,0,0); } } } if(ans==1e9) 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...