Submission #753765

#	Time	Username	Problem	Language	Result	Execution time	Memory
753765		acceptify	Race (IOI11_race)	C++17	100 / 100	882 ms	42340 KiB

race

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

const int mxn = 2e5 + 5;

vector<pair<int, int>> adj[mxn];
int del[mxn], sz[mxn];
map<int, int> mp;
vector<pair<int, int>> tmp;
int res = 2e9;

void dfs(int x, int par = -1) {
    sz[x] = 1;
    for (auto [w, p] : adj[x]) {
        if (p == par || del[p]) continue;
        dfs(p, x);
        sz[x] += sz[p];
    }
}

int centroid(int x, int n, int par = -1) {
    for (auto [w, p] : adj[x]) {
        if (p == par || del[p]) continue;
        if (sz[p] * 2 > n) return centroid(p, n, x);
    }
    return x;
}

void dfs2(int k, int x, int par, int dis, int cnt) {
    if (dis > k) return;
    tmp.push_back({dis, cnt});
    if (mp.find(k - dis) != mp.end()) res = min(res, mp[k - dis] + cnt);
    for (auto [w, p] : adj[x]) {
        if (p == par || del[p]) continue;
        dfs2(k, p, x, dis + w, cnt + 1);
    }
}

void solve(int k, int x) {
    dfs(x);
    int c = centroid(x, sz[x]);
    mp.clear(), tmp.clear();
    mp[0] = 0;
    for (auto [w, i] : adj[c]) {
        if (!del[i]) {
            dfs2(k, i, c, w, 1);
            for (auto [d, c] : tmp) {
                if (mp.find(d) == mp.end()) mp[d] = c;
                else mp[d] = min(mp[d], c);
            }
            tmp.clear();
        }
    }
    del[c] = 1;
    for (auto [w, i] : adj[c]) {
        if (!del[i]) solve(k, i);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N - 1; i++) {
        adj[H[i][0]].push_back({L[i], H[i][1]});
        adj[H[i][1]].push_back({L[i], H[i][0]});
    }
    solve(K, 0);
    if (res == 2e9) return -1;
    return res;
}

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