Submission #1131093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131093		a5a7	Race (IOI11_race)	C++20	100 / 100	519 ms	98296 KiB

race

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int best_path(int N, int K, int H[][2], int L[]){
    map<ll,int> m[N];
    vector<vector<pair<int,int>>> adj(N);
    for (int i = 1; i < N; i++){
        adj[H[i-1][0]].push_back({H[i-1][1], L[i-1]});
        adj[H[i-1][1]].push_back({H[i-1][0], L[i-1]});
    }
    ll dist = 0;
    int best = N+1;
    int depth = 0;
    function<void(int,int)> dfs = [&](int x, int prev){
        m[x][dist] = depth;
        depth++;
        for (auto nxt : adj[x]){
            if (nxt.first == prev) continue;
            dist += nxt.second;
            dfs(nxt.first, x);
            dist -= nxt.second;
            if (m[x].size()<m[nxt.first].size()) m[x].swap(m[nxt.first]);
            for (auto y : m[nxt.first]){
                if (!m[x].count(K+2*dist-y.first)) continue;
                best = min(best, m[x][K+2*dist-y.first]+y.second-2*depth+2);
            }
            for (auto y : m[nxt.first]){
                if (m[x].count(y.first)){
                    m[x][y.first] = min(m[x][y.first], y.second);
                }else{
                    m[x][y.first] = y.second;
                }
            }
        }
        depth--;
    };
    dfs(0, -1);
    if (best == (N+1)) best = -1;
    return best;
}

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