Submission #575689

#	Time	Username	Problem	Language	Result	Execution time	Memory
575689		web	Race (IOI11_race)	C++17	21 / 100	3095 ms	19096 KiB

race

#include <map>
#include <math.h>
#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, int bestPoss, int currBest)
{
    if (depth > currBest)
        return -1;
  ////cout<<"curr node "<<currNode<<endl;
  if(costUsed == K)
    return depth;
  if(costUsed > K)
    return -1;
  int bestL = INT_MAX;
  for(auto node : adjList[currNode])
  {
   ////cout<<"child: "<<node.first<<endl; 
    if(node.first == parentNode)
      continue;
    int l = DFS(node.first, currNode, costUsed+node.second, depth+1, K, bestPoss, currBest);
    ////cout<<"l = "<<l<<endl;
    if(l < bestL && l!= -1)
      {bestL = l;
    
        ////cout<<"new best L"<<endl;
      }

    if (bestL == bestPoss)
        return bestL;
  }
  if(bestL ==INT_MAX)
    return -1;
  return bestL;
}

int best_path(int N, int K, int H[][2], int L[])
{
    int maxWEdge = 0;
  for(int i  =0; i<N-1; ++i)
  {
   
    if(L[i] > K)
      continue;
    if (L[i] > maxWEdge)
        maxWEdge = L[i];
    //cout<<"want to add edge "<<i<<endl;
    //cout<<H[i][0]<<" "<<H[i][1]<<" "<<L[i]<<endl;
    if(indices.find( H[i][0]) == indices.end())
    {
        //cout<<"made new index"<<endl;
        
        indices[H[i][0]] = adjList.size();
        //cout<<H[i][0] <<" => "<<adjList.size()<<endl;
        adjList.push_back({});
    }
    
   
    if(indices.find( H[i][1]) == indices.end())
    {
        //cout<<"made new index"<<endl;
        indices[H[i][1]] = adjList.size();
        //cout<<H[i][1] <<" => "<<adjList.size()<<endl;
        adjList.push_back({});
    }
    //cout<<"added {" <<indices[H[i][0]]<<" "<<L[i]<<"}"<<" to " << H[i][1]<<endl;
    //cout << "added {" << indices[H[i][1]] << " " << L[i] << "}" << " to " << H[i][0] << endl;
    adjList[indices[H[i][1]]].push_back({indices[H[i][0]], L[i]});
    adjList[indices[H[i][0]]].push_back({ indices[H[i][1]], L[i] });
  }

  for(auto node: adjList)
  { 
  //cout<<endl;
    for(auto edge: node)
    {
      //cout<<"edge: "<<edge.first<<" "<<edge.second<<endl;
    }
  }
  
  //////cout<<"here"<<endl;
  int bestPath = INT_MAX;
  int bestPossDepth = (floor(static_cast<long double>(K) / static_cast<long double> (maxWEdge)));
  for(int i  =0 ; i<adjList.size(); ++i)
  {
      int l  = DFS(i, -1, 0, 0, K, bestPossDepth, bestPath);
      ////////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;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:84:14: warning: variable 'edge' set but not used [-Wunused-but-set-variable]
   84 |     for(auto edge: node)
      |              ^~~~
race.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(int i  =0 ; i<adjList.size(); ++i)
      |                   ~^~~~~~~~~~~~~~~

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