Submission #434350

#	Time	Username	Problem	Language	Result	Execution time	Memory
434350		Apiram	Race (IOI11_race)	C++14	0 / 100	4 ms	5792 KiB

race

//#include "race.h"
#include<bits/stdc++.h>
using namespace std;
struct point{
  int u,x,y;
};
vector<int>dp(2e5,0);
vector<vector<pair<int,int>>>adj(2e5);
/*void dfs(int j ,int par){
  for (auto x:adj[j]){
    if (x.first!=par){
      
    }
  }
}*/
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]});
  }
  //dfs(0,-1);
  queue<point>q;
  point p;
  p.u=0,p.x=0,p.y=0;
  q.push(p);
  int ans=INT_MAX;
  vector<bool>visited(N,false);
  while(!q.empty()){
    p=q.front();
    q.pop();
    if (p.x==K){
      ans=min(ans,p.y);
      continue;
    }
    if (p.x>K)break;
    for (auto x:adj[p.u]){
      if (!visited[x.first]){
        visited[x.first]=true;
         point a;
         a.u = x.first;
         a.x = p.x + x.second;
         a.y = p.y + 1;
         q.push(a);
         a.x-=p.x;
         a.y=1;
         q.push(a);

      }
    }
  }
  if (ans==INT_MAX)return -1;
  return ans;
}

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