Submission #1037480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037480		ArthuroWich	Race (IOI11_race)	C++17	21 / 100	3034 ms	18512 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];
unordered_map<int, int> occ[2];
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) {
    if (path > k) {
        return;
    }
    if (occ[1].find(path) == occ[1].end()) {
        occ[1][path] = d;
    } else {
        occ[1][path] = min(occ[1][path], d);
    }
    if (k == path) {
        ans = min(ans, d);
    } else if (occ[0].find(k-path) != occ[0].end()) {
        ans = min(ans, d+occ[0][k-path]);
    }
    for (auto [j, w] : adj[i]) {
        if (proc[j] || j == p) {
            continue;
        }
        calc(j, i, d+1, path+w);
    }
}
void decompose(int i) {
    dfs(i, -1);
    if (si[i] == 1) {
        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);
        if (occ[0].size() < occ[1].size()) {
            occ[0].swap(occ[1]);
        }
        for (auto c : occ[1]) {
            if (occ[0].find(c.first) != occ[0].end()) {
                occ[0][c.first] = min(occ[0][c.first], c.second);
            } else {
                occ[0][c.first] = c.second;
            }
        }
        occ[1].clear();
    }
    occ[0].clear();
    for (auto [j, w] : adj[i]) {
        if (proc[j]) {
            continue;
        }
        decompose(j);
    }
}
int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    occ[0].reserve(200000);
    occ[1].reserve(200000);
    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(1);
    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