Submission #1037475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037475		ArthuroWich	Race (IOI11_race)	C++17	21 / 100	254 ms	262144 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
int n, k, ans = INT_MAX, proc[200005], si[200005];
vector<pair<int, int>> adj[200005];
map<int, int> occ[22][200005];
void dfs(int i, int p) {
    si[i] = 1;
    for (auto [j, _] : adj[i]) {
        if (proc[j] || j == p) {
            continue;
        }
        dfs(j, i);
        si[i] += si[j];
    }
}
int centroid(int i, int p, int s) {
    for (auto [j, w] : adj[i]) {
        if (proc[j] || j == p) {
            continue;
        }
        if (si[j] > s/2) {
            return centroid(j, i, s);
        }
    }
    return i;
}
void calc(int i, int p, int d, int path, int l, int h, int c) {
    if (path > k) {
        return;
    }
    if (occ[l][h].find(path) == occ[l][h].end()) {
        occ[l][h][path] = d;
    } else {
        occ[l][h][path] = min(occ[l][h][path], d);
    }
    if (k == path) {
        ans = min(ans, d);
    } else if (occ[l][c].find(k-path) != occ[l][c].end()) {
        ans = min(ans, d+occ[l][c][k-path]);
    }
    for (auto [j, w] : adj[i]) {
        if (proc[j] || j == p) {
            continue;
        }
        calc(j, i, d+1, path+w, l, h, c);
    }
}
void decompose(int i, int l) {
    dfs(i, -1);
    if (si[i] == 1 || proc[i]) {
        return;
    }
    i = centroid(i, -1, si[i]);
    proc[i] = 1;
    for (auto [j, w] : adj[i]) {
        if (proc[j]) {
            continue;
        }
        calc(j, i, 1, w, l, j, i);
        if (occ[l][i].size() < occ[l][j].size()) {
            occ[l][i].swap(occ[l][j]);
        }
        for (auto c : occ[l][j]) {
            if (occ[l][i].find(c.first) != occ[l][i].end()) {
                occ[l][i][c.first] = min(occ[l][i][c.first], c.second);
            } else {
                occ[l][i][c.first] = c.second;
            }
        }
    }
    for (auto [j, w] : adj[i]) {
        if (proc[j]) {
            continue;
        }
        decompose(j, l+1);
    }
}
int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    for (int i = 0; i < n-1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    decompose(0, 0);
    if (ans == INT_MAX) {
        return -1;
    } else {
        return ans;
    }
}

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