Submission #434360

#	Time	Username	Problem	Language	Result	Execution time	Memory
434360		Apiram	Race (IOI11_race)	C++14	21 / 100	3056 ms	11076 KiB

race

//#include "race.h"
#include<bits/stdc++.h>
using namespace std;
struct point{
  int u,x,y,par;
};
int ans=INT_MAX;

vector<vector<pair<int,int>>>adj(2e5);
void dfs(int j,int score,int level,int par,int K){
  if (score>K)return ;
  if (score==K){
    ans=min(ans,level);
    return ;
  }
  for (auto x:adj[j]){
    if (x.first!=par){
      dfs(x.first,score+x.second,level+1,j,K);
    }
  }
}
int best_path(int N, int K, int H[][2], int L[])
{
  for (int i  =0;i<N-1;++i){
    adj[H[i][0]].push_back({H[i][1],L[i]});
    adj[H[i][1]].push_back({H[i][0],L[i]});
  }
	for (int i =0;i<N;++i)
  	dfs(i,0,0,-1,K);
 
  if (ans==INT_MAX)return -1;
  return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57