제출 #422208

#제출 시각아이디문제언어결과실행 시간메모리
422208ScarletS경주 (Race) (IOI11_race)C++17
0 / 100
7 ms6476 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1<<18, INF = 1e9; int k, x, y, ans = INF, dp[1<<20], sub[N]; array<int,2> a[N]; array<int,4> d[N]; vector<array<int,2>> e[N]; bitset<N> b; void subDfs(int c, int p) { sub[c]=1; for (auto i : e[c]) if (i[0]!=p&&!b[i[0]]) { subDfs(i[0],c); sub[c]+=sub[i[0]]; } } int findC(int c, int p, int t) { for (auto i : e[c]) if (i[0]!=p&&!b[i[0]]&&sub[i[0]]>t) return findC(i[0],c,t); return c; } void dfs(int c, int p, int h) { int z=1; d[0]={c,p,h,1}; for (int i=0;i<z;++i) { for (int j=0;j<4;++j) cout<<d[i][j]<<" "; cout<<"\n"; a[x++]={d[i][2],d[i][3]}; ans=min(ans,dp[k-d[i][2]]+d[i][3]); for (auto j : e[d[i][0]]) if (j[0]!=d[i][1]&&d[i][2]+j[1]<=k) d[z++]={j[0],d[i][0],d[i][2]+j[1],d[i][3]+1}; } //cout<<"---\n"; } void solve(int n) { subDfs(n,-1); int c = findC(n,-1,sub[n]/2); b[c]=1; x=0; for (auto i : e[c]) if (!b[i[0]]&&i[1]<=k) { y=x; dfs(i[0],c,i[1]); for (int j=y;j<x;++j) dp[a[j][0]]=min(dp[a[j][0]],a[j][1]); } for (int i=0;i<x;++i) dp[a[i][0]]=INF; for (auto i : e[c]) if (!b[i[0]]) solve(i[0]); } int best_path(int n, int K, int h[][2], int l[]) { k=K; for (int i=0;i<n-1;++i) { e[h[i][0]].push_back({h[i][1],l[i]}); e[h[i][1]].push_back({h[i][0],l[i]}); } for (int i=1;i<=k;++i) dp[i]=INF; solve(0); 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...