Submission #824216

#	Time	Username	Problem	Language	Result	Execution time	Memory
824216		Mouad_ouj	Race (IOI11_race)	C++17	21 / 100	3070 ms	8088 KiB

race

#include<bits/stdc++.h>
using namespace std;
int ans=1000001,n,k;
vector<vector< pair<int,int>> > tree;
void dfs(int node,int par,int dis,int cur)
{
    for(int x=0;x<tree[node].size();x++)
    { 
        int to=tree[node][x].first;
        if(par==to)continue;
        if(dis+tree[node][x].second>k)
        continue;
        if(dis+tree[node][x].second==k)
        {
            ans=min(ans,cur+1);
            continue;
        }
        dfs(to,node,dis+tree[node][x].second,cur+1);
    }
}
int best_path(int N,int K,int bet[][2],int w[])
{
    n=N;
    k=K;
    tree.resize(n+1);
    for(int x=0;x<n-1;x++)
    {
        tree[bet[x][0]].push_back(make_pair(bet[x][1],w[x]));
        tree[bet[x][1]].push_back(make_pair(bet[x][0],w[x]));
    }
    for(int x=0;x<n;x++)
        dfs(x,-1,0,0);
    if(ans!=1000001)
    return ans;
    return -1; 
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:7: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]
    7 |     for(int x=0;x<tree[node].size();x++)
      |                 ~^~~~~~~~~~~~~~~~~~

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