Submission #575657

#	Time	Username	Problem	Language	Result	Execution time	Memory
575657		web	Race (IOI11_race)	C++17	0 / 100	1 ms	340 KiB

race

#include <map>
#include <iostream>
#include <climits>
#include "race.h"
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;

vector<vector<pair<int, long long>>> adjList;


map<int,int> indices;
int DFS(int currNode, int parentNode, int costUsed, int depth, int K)
{
  //cout<<"curr node "<<currNode<<endl;
  if(costUsed == K)
    return depth;
  if(costUsed > K)
    return -1;
  int bestL = INT_MAX;
  for(auto node : adjList[indices[currNode]])
  {
  
  
   //cout<<"child: "<<node.first<<endl; 
    if(node.first == parentNode)
      continue;
    int l = DFS(node.first, currNode, costUsed+node.second, depth+1, K);
    //cout<<"l = "<<l<<endl;
    if(l < bestL && l!= -1)
      {bestL = l;
        //cout<<"new best L"<<endl;
      }
  }
  if(bestL ==INT_MAX)
    return -1;
  return bestL;
}

int best_path(int N, int K, int H[][2], int L[])
{
 
  for(int i  =0; i<N-1; ++i)
  {
    
    if(L[i] > 100)
      continue;
    if(indices.find( H[i][0]) == indices.end())
    {
        indices[H[i][0]] = adjList.size();
        adjList.push_back({});
    }
    adjList[indices[H[i][0]]].push_back({H[i][1], L[i]});
    if(indices.find( H[i][1]) == indices.end())
    {
        indices[H[i][1]] = adjList.size();
        adjList.push_back({});
    }
    adjList[indices[H[i][1]]].push_back({H[i][0], L[i]});
  }
  ////cout<<"here"<<endl;
  int bestPath = INT_MAX;
  for(int i  =0 ; i<N; ++i)
  {
      int l  = DFS(i, -1, 0, 0, K);
      //////cout<<"DFS sur"<<endl;
      if(l != -1 && l < bestPath)
        bestPath = l;

      if(bestPath == 1)
        break;
  }
  ////cout<<"there"<<endl;
  if(bestPath == INT_MAX)
    return -1;
  return bestPath;
}

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