Submission #499790

#	Time	Username	Problem	Language	Result	Execution time	Memory
499790		HappyPacMan	Race (IOI11_race)	C++14	9 / 100	3080 ms	34716 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 15;
vector<pair<int,int> > adj[MAXN];
map<long long,int> cost[MAXN];
int res = MAXN;

void dfs(int u,int p,long long k,long long d,int l){
    cost[u][d] = l;
    for(auto v : adj[u]){
        if(v.first == p) continue;
        dfs(v.first,u,k,d+v.second,l+1);
        if(cost[u].size() < cost[v.first].size()) swap(cost[u],cost[v.first]);
        for(auto w : cost[v.first]){
            long long split = k - w.first + 2*d;
            if(cost[v.first].count(split)) res = min(res,w.second+cost[v.first][split]-2*l);
            if(cost[u].count(w.first)) cost[u][w.first] = min(cost[u][w.first],w.second);
            else cost[u][w.first] = w.second;
        }
    }
    if(cost[u].count(d+k)) res = min(res,cost[u][d+k]-l);
}

int best_path(int N, int K, int H[][2], int L[]){
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].emplace_back(H[i][1],L[i]);
        adj[H[i][1]].emplace_back(H[i][0],L[i]);
    }
    int temp = -1;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) cost[j].clear();
        res = MAXN;
        dfs(0,0,K,0,0);
        if(res != MAXN){
            if(temp != -1){
                assert(temp == res);
                temp = res;
            }
        }
    }
    if(res == MAXN) res = -1;
    return res;
}

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