제출 #369217

#제출 시각아이디문제언어결과실행 시간메모리
369217chubyxdxd경주 (Race) (IOI11_race)C++14
9 / 100
3064 ms7532 KiB
#include "race.h" #include <bits/stdc++.h> #define sc second #define ff first /*#include <stdio.h> #include <stdlib.h> #define MAX_N 500000 static int N, K; static int H[MAX_N][2]; static int L[MAX_N]; static int solution; */ using namespace std; typedef pair<int,int> ii; int mini=1e9; int k; /*inline void my_assert(int e) {if (!e) abort();} void read_input() { int i; my_assert(2==scanf("%d %d",&N,&K)); for(i=0; i<N-1; i++) my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i])); my_assert(1==scanf("%d",&solution)); } */ vector<vector<ii>> G; void dfs(int node,int pad,int sum,int num){ if(sum==k){ mini=min(num,mini); return; } if(sum>k)return; for(auto i:G[node]){ if(i.ff==pad)continue; if(sum+i.sc>k)return; dfs(i.ff,node,sum+i.sc,num+1); } } int best_path(int N, int K, int H[][2], int L[]) { k=K; G.assign(N+2,vector<ii>()); for(int i=0;i<N-1;i++){ int a=H[i][0]; int b=H[i][1]; G[a].emplace_back(ii(b,L[i])); G[b].emplace_back(ii(a,L[i])); } mini=1e9; for(int i=0;i<N;i++){ dfs(i,i,0,0); } if(mini==1e9)mini=-1; return mini; } /* int main() { int ans; read_input(); ans = best_path(N,K,H,L); if(ans==solution) printf("Correct.\n"); else printf("Incorrect. Returned %d, Expected %d.\n",ans,solution); return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...