제출 #1199683

#제출 시각아이디문제언어결과실행 시간메모리
1199683ricardsjansonsRace (IOI11_race)C++20
9 / 100
1235 ms327680 KiB
#include "race.h" #include <bits/stdc++.h> #define ll long long using namespace std; const int INF=1e9; int better(int a,int b){ if(!a){ return b; } if(!b){ return a; } return min(a,b); } int KMAX; vector<vector<pair<int,int>>>adj; map<pair<int,int>,map<int,int>>mem; map<int,int>dfs(int u,int p){ if(mem.count({u,p})){ return mem[{u,p}]; } map<int,int>&res=mem[{u,p}]; res[0]=0; for(auto[v,l]:adj[u]){ if(v==p){ continue; } for(auto[s,c]:dfs(v,u)){ if(s+l>KMAX){ continue; } res[s+l]=better(res[s+l],c+1); } } return res; } int best_path(int N, int K, int H[][2], int L[]) { KMAX=K; adj.resize(N); for(int i=0;i<N-1;i++){ auto[u,v]=H[i]; int l=L[i]; adj[u].push_back({v,l}); adj[v].push_back({u,l}); } int res=0; for(int u=0;u<N;u++){ for(auto[v,l]:adj[u]){ //cout<<"! "<<u<<" "<<v<<" "<<dfs(v,u)[K]<<"\n"; res=better(res,dfs(v,u)[K]); } } return (res?res:-1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...