Submission #1162062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162062		dragdam	Race (IOI11_race)	C++17	100 / 100	338 ms	76204 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5+5;
const int inf = 2e9;


int n, r;
vector<array<int,2>> g[MAXN];
int ans;
array<int,2> d[MAXN];
map<int,int> sg[MAXN];

void dfs(int x, int p){
    sg[x][d[x][1]] = d[x][0];
    for(auto [k,w] : g[x]){
        if(k==p) continue;
        d[k][0] = d[x][0]+1;
        d[k][1] = d[x][1]+w;
        dfs(k,x);
        if(sg[k].size() > sg[x].size()){
            swap(sg[x], sg[k]);
        }
        for(auto p : sg[k]){
            int t = r+2*d[x][1]-p.first;
            if(sg[x].find(t)!=sg[x].end()) ans = min(ans, p.second+sg[x][t]-2*d[x][0]);
        }
        for(auto p : sg[k]){
            if(sg[x].find(p.first)!=sg[x].end()) sg[x][p.first] = min(sg[x][p.first], p.second);
            else sg[x][p.first] = p.second;
        }
        sg[k].clear();
    }
}

int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]){
    n = N; r = K;
    ans = inf;
    for(int i = 0; i < n; ++i){
        g[i].clear();
        sg[i].clear();
    }
    for(int i = 0; i < n-1; ++i){
        int x = H[i][0], y = H[i][1], w = L[i];
        g[x].push_back({y,(long long)w});
        g[y].push_back({x,(long long)w});
    }
    dfs(0,0);
    return (ans==inf ? -1 : ans);
}

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