Submission #824201

#	Time	Username	Problem	Language	Result	Execution time	Memory
824201		Mouad_ouj	Race (IOI11_race)	C++17	31 / 100	240 ms	114412 KiB

race

#include<bits/stdc++.h>
using namespace std;
int dp[200001][101],ans=200001,n,k;
vector<vector< pair<int,int>> > tree;
void dfs(int node,int par)
{
    for(int x=0;x<tree[node].size();x++)
    {
        int to=tree[node][x].first;
        int dis=tree[node][x].second;
        if(par==to)
        continue;
        dfs(to,node);
        for(int x=0;x<=k-dis;x++)
        ans=min(ans,dp[node][x]+dp[to][k-dis-x]+1);   //f sub sol
        for(int x=0;x+dis<=k;x++)
        dp[node][x+dis]=min(dp[node][x+dis],dp[to][x]+1); //s sub sol
    }
}
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<200001;x++)
    {
       for(int y=0;y<101;y++)
       dp[x][y]=200001;
    }
    for(int x=0;x<n;x++)
       dp[x][0]=0;
    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]));
    }
    dfs(0,-1);
    if(ans!=200001)
    return ans;
    return -1;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(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: 0 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57