Submission #329291

#	Time	Username	Problem	Language	Result	Execution time	Memory
329291		ryangohca	Race (IOI11_race)	C++17	100 / 100	458 ms	108976 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long, long long>
long long n, k;
vector<pii> adjlist[200000];
long long dep[200000];
long long off[200000];
long long ans = 1<<30;
set<pii> *dfs(long long n, long long p, long long d){
    dep[n] = d;
    set<pii> *cur = new set<pii>();
    for (auto [i, cost] : adjlist[n]){
        if (i == p) continue;
        set<pii> *child = dfs(i, n, d + 1);
        if (cur->size() < child->size()){
            for (auto [path, depth] : *cur){
                auto itr = child->lower_bound({k - (path + off[n]) - cost - off[i], 0});
                if (itr != child->end()){
                    if ((*itr).first == k - (path + off[n]) - cost - off[i]){
                        ans = min(ans, (*itr).second + depth - 2*d);
                    }
                }
            }
            for (auto [path, depth] : *cur){
                long long newp = path + off[n] - off[i] - cost;
                child->insert({newp, depth});
            }
            off[n] = off[i] + cost;
            swap(child, cur);
        } else {
            for (auto [path, depth] : *child){
                long long actual = path + off[i] + cost;
                auto itr = cur->lower_bound({k - actual - off[n], 0});
                if (itr != cur->end()){
                    if ((*itr).first == k - actual - off[n]){
                        ans = min(ans, (*itr).second + depth - 2*d);
                    }
                }
            }
            for (auto [path, depth] : *child){
                cur->insert({path + off[i] + cost - off[n], depth});
            }
        }
    }
    cur->insert({-off[n], d});
    auto itr = cur->lower_bound({k - off[n], 0});
    if (itr != cur->end()){
        if ((*itr).first == k - off[n]){
            ans = min(ans, (*itr).second - d);
        }
    }
    return cur;
}
int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    k = K;
    for (int i = 0; i < N - 1; i++){
        adjlist[H[i][0]].push_back({H[i][1], L[i]});
        adjlist[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs(0, -1, 0);
    if (ans == (1<<30)) return -1;
    else return ans;
}

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