Submission #1131058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131058		a5a7	Race (IOI11_race)	C++20	21 / 100	578 ms	327680 KiB

race

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

int best_path(int N, int K, int H[][2], int L[]){
    map<int,int> m[N];
    map<int,int> m2[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]});
    }
    int back[N];
    fill(back, back+N, 0);
    int best = N+1;
    function<void(int,int)> dfs = [&](int x, int prev){
        m[x][0] = 0;
        for (auto nxt : adj[x]){
            if (nxt.first == prev) continue;
            back[nxt.first] = nxt.second;
            dfs(nxt.first, x);
            if (m2[nxt.first].size()>m[x].size()) m[x].swap(m2[nxt.first]);
            for (auto y : m2[nxt.first]){
                if (m[x].count(K-y.first)){
                    best = min(best, m[x][K-y.first]+y.second);
                }
            }
            for (auto y : m2[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;
                }
            }
        }
        for (auto y : m[x]){
            m2[x][y.first+back[x]] = y.second+1;
        }
    };
    dfs(0, -1);
    if (best == (N+1)) best = -1;
    return best;
}

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