Submission #229657

#	Time	Username	Problem	Language	Result	Execution time	Memory
229657		DavidDamian	Race (IOI11_race)	C++11	21 / 100	56 ms	12664 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 2
///N Searches
typedef long long ll;
struct edge
{
    int to;
    ll w;
};
vector<edge> adjList[200005];
int k;
int minimum=INT_MAX;
void dfs_sub2(int u,int p,int depth,int path)
{
    if(path==k) minimum=min(minimum,depth);
    for(edge e: adjList[u]){
        int v=e.to;
        ll w=e.w;
        if(p==v) continue;
        dfs_sub2(v,u,depth+1,path+w);
    }
}
int best_path(int n, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0;i<n-1;i++){
        int a=H[i][0];
        int b=H[i][1];
        ll w=L[i];
        adjList[a].push_back({b,w});
        adjList[b].push_back({a,w});
    }
    if(n<=1000){
        for(int u=0;u<n;u++){
            dfs_sub2(u,-1,0,0);
        }
        return (minimum!=INT_MAX)? minimum : -1;
    }
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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