Submission #115105

#	Time	Username	Problem	Language	Result	Execution time	Memory
115105		oolimry	Race (IOI11_race)	C++14	43 / 100	3035 ms	255824 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;

static vector<ii> adj[200005];
static bool vis[200005];
static unordered_map<int,int> dp[200005];
int k;
int ans = 102345678;
void dfs(int u){
    vis[u] = true;
    for(int i = 0;i < adj[u].size();i++){
        int v = adj[u][i].first;
        int w = adj[u][i].second;

        if(vis[v]) continue;
        dfs(v);
        vector<ii> updates;
        for(ii x : dp[v]){
            int value = w + x.first;
            if(value <= k){
                if(dp[u].find(k-value) != dp[u].end()){
                    ans = min(ans, dp[u][k-value] + x.second + 1);
                }
                updates.push_back({value,x.second+1});
            }
        }
        dp[v].clear();

        for(ii x : updates){
            if(dp[u].find(x.first) == dp[u].end()){
                dp[u][x.first] = x.second;
            }
            else{
                dp[u][x.first] = min(x.second,dp[u][x.first]);
            }
        }
    }

    /*
    cout << u << ": ";
    for(ii x : dp[u]){
        cout << "(" << x.first << ", " << x.second << ") ";
    }
    cout << "\n";
    */
}
int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    int n = N;
    for(int i = 0;i < n;i++) dp[i][0] = 0;
    for(int i = 0;i < n-1;i++){
        int a = H[i][0];
        int b = H[i][1];
        int c = L[i];
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    dfs(0);
    if(ans > n) return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int)':
race.cpp:15:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adj[u].size();i++){
                   ~~^~~~~~~~~~~~~~~

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