Submission #115135

#	Time	Username	Problem	Language	Result	Execution time	Memory
115135		oolimry	Race (IOI11_race)	C++14	100 / 100	820 ms	79552 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];
unordered_map<int,int> dp[200005];
ii offset[200005]; ///values in dp[u] are actually offset[u] more than what is in the maps, first->first, second->second
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;
        bool isSwap = false;
        if(dp[v].size() > dp[u].size()){
            isSwap = true;
            swap(dp[u],dp[v]);
            swap(offset[u], offset[v]);
            offset[u].first += w;
            offset[u].second++;
        }
        for(ii x : dp[v]){

            int value = x.first + offset[v].first; ///w/o offsets
            int cost = x.second + offset[v].second; ///w/o offsets
            if(!isSwap){
                value += w;
                cost++;
            }
            //if(i == 0) cout << value << " " << cost << " " << offset[v].second << "\n";
            if(value <= k){
                if(dp[u].find(k - value - offset[u].first) != dp[u].end()){
                    ans = min(ans, dp[u][k - value - offset[u].first] + offset[u].second + cost);
                }
                updates.push_back({value,cost});
            }
        }
        dp[v].clear();

        for(ii x : updates){
            if(dp[u].find(x.first - offset[u].first) == dp[u].end()){
                dp[u][x.first - offset[u].first] = x.second - offset[u].second;
            }
            else{
                dp[u][x.first - offset[u].first] = min(x.second - offset[u].second,dp[u][x.first - offset[u].first]);
            }
        }
    }
    /*
    cout << u << " " << offset[u].first << " " << offset[u].second << ": ";
    for(ii x : dp[u]){
        cout << "(" << x.first + offset[u].first << ", " << x.second + offset[u].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:16: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: 57 / 57