Submission #1097825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097825		SiddharthJoshi6263	Race (IOI11_race)	C++17	21 / 100	1230 ms	262144 KiB

race

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (long long)(x).size()
#define pii pair<long long, long long>

long long ANS = LLONG_MAX;

void dfs_sze(long long u, long long par, vector<vector<pii>> &adj, vector<long long> &sze, vector<long long> &len, vector<long long> &depth) {
    sze[u] = 1;
    for (auto v : adj[u]) {
        if (v.f != par) {
            len[v.f] = len[u] + v.s;
            depth[v.f] = depth[u] + 1;
            dfs_sze(v.f, u, adj, sze, len, depth);
            sze[u] += sze[v.f];
        }
    }
}

void small_to_large_merging(long long K, long long u, long long par, vector<long long> &sze, vector<long long> &len, vector<long long> &depth, vector<vector<pii>> &adj, vector<multiset<pii>> &sets) {
    multiset<pii> smalls1, smalls2;
    for (auto x : adj[u]) {
        if (x.f != par) {
            small_to_large_merging(K, x.f, u, sze, len, depth, adj, sets);
            for (auto y : sets[x.f]) {
                long long len1 = y.f - len[u];
                long long dep = y.s - depth[u];
                pii find = {K - len1, -1ll};
                auto it = smalls2.lower_bound(find);
                if (it != smalls2.end()) {
                    if (it->f == find.f) {
                        ANS = min(ANS, dep + it->s);
                    }
                }
            }
            for (auto y : sets[x.f]) {
                smalls1.insert(y);
                smalls2.insert({y.f - len[u], y.s - depth[u]});
            }
        }
    }
    sets[u] = smalls1;  // Do not clear after this assignment
    sets[u].insert({len[u], depth[u]});  // Include the current node's length and depth

    pii find = {K + len[u], -1ll};
    auto it = sets[u].lower_bound(find);
    if (it != sets[u].end()) {
        if (it->f == find.f) {
            ANS = min(ANS, it->s - depth[u]);
        }
    }
}

int best_path(int N, int k, int H[][2], int L[]) {
    ANS = LLONG_MAX;
    long long n = N, K = k;

    vector<vector<pii>> adj(n);
    for (long long i = 0; i < n - 1; i++) {
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }

    vector<long long> sze(n, 0);
    vector<long long> len(n, 0);
    vector<long long> depth(n, 0);
    dfs_sze(0, -1, adj, sze, len, depth);

    vector<multiset<pii>> sets(n);
    small_to_large_merging(K, 0, -1, sze, len, depth, adj, sets);

    if (ANS == LLONG_MAX) {
        return -1;
    }
    return ANS;
}

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