Submission #306973

#	Time	Username	Problem	Language	Result	Execution time	Memory
306973		amunduzbaev	Race (IOI11_race)	C++14	21 / 100	3065 ms	10616 KiB

race

#include "race.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;


vector< pair<int,int> > v[200005];
int used[200005],now,k;


// find length ans time treveled  from now to vi
int ans=INT_MAX;
void fun(int vi,int cnt,int num){
    //cout<<now<<" "<<vi<<" "<<cnt<<" "<<num<<'\n';
    if(cnt>=k){
        if(cnt==k)
            ans=min(ans,num);
        return ;
    }

    num++;
    for(int i=0;i<v[vi].size();i++){
        if(used[v[vi][i].first]) continue;
        //cout<<vi<<" "<<v[vi][i].first<<" \n";
        used[v[vi][i].first]=1;
        fun(v[vi][i].first,v[vi][i].second+cnt,num);
    }
}


int best_path(int n, int K, int h[][2], int l[])
{
    k=K;
    // converting array into paired vector
    // v[a]={b,t}
    // there are road from city a to b length of t
    for(int i=0;i<n-1;i++){
        v[h[i][0]].push_back({h[i][1],l[i]});
        v[h[i][1]].push_back({h[i][0],l[i]});
    }
    // finding lenghtes
    for(int i=0;i<n;i++){
        now=i;
        used[i]=1;
        fun(i,0,0);
        memset(used,0,sizeof(used));
    }


    ans=(ans==INT_MAX ? -1:ans);
  return ans;
}

/*

4 3
0 1 1
1 2 2
1 3 4
2

*/

Compilation message (stderr)

race.cpp: In function 'void fun(int, int, int)':
race.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<v[vi].size();i++){
      |                 ~^~~~~~~~~~~~~

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