Submission #1244350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244350		enjeeeff	Race (IOI11_race)	C++20	21 / 100	3094 ms	32468 KiB

race

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include"race.h"
typedef long long ll;
#define vec vector
using namespace std;

struct Edge {
    ll to, w;
};

const ll maxn = 2e5 + 1;
const ll maxk = 1e6 + 1;
ll ans, k, t = 0;
vec<Edge> adj[maxn];
ll deleted[maxn], ofLength[maxk], s[maxn], lastUpdate[maxk];

void find_sizes(ll v, ll p = -1) {
    s[v] = 1;
    for (auto &e : adj[v])
        if (!deleted[e.to] && e.to != p) {
            find_sizes(e.to, v);
            s[v] += s[e.to];
        }
}

ll find_centroid(ll v, ll n, ll p = -1) {
    for (auto &e : adj[v])
        if (!deleted[e.to] && e.to != p && s[e.to] * 2 > n)
            return find_centroid(e.to, n, v);
    return v;
}

void use_dfs(ll v, ll dist, ll dist1 = 1, ll p = -1) {
    for (auto &e : adj[v])
        if (!deleted[e.to] && e.to != p)
            use_dfs(e.to, dist + e.w, dist1 + 1, v);
    if (dist > k) return;
    if (lastUpdate[k - dist] == t)
        ans = min(ans, ofLength[k - dist] + dist1);
    if (dist == k)
        ans = min(ans, dist1);
}

void apply_dfs(ll v, ll dist, ll dist1 = 1, ll p = -1) {
    for (auto &e : adj[v])
        if (!deleted[e.to] && e.to != p)
            apply_dfs(e.to, dist + e.w, dist1 + 1, v);
    if (dist > k) return;
    if (lastUpdate[dist] < t)
        ofLength[dist] = dist1;
    else
        ofLength[dist] = min(ofLength[dist], dist1);
    lastUpdate[dist] = t;
}

void divide(ll v = 0) {
    find_sizes(v);
    ll cent = find_centroid(v, s[v]);
    deleted[cent] = 1;

    t++;
    for (auto &e : adj[cent]) {
        use_dfs(e.to, e.w);
        apply_dfs(e.to, e.w);
    }

    // for (auto &l : usedLengths)
    //     ofLength[l] = 1e9;
    // usedLengths.clear();

    for (auto &e : adj[cent])
        if (!deleted[e.to])
            divide(e.to);
}

// int main() {
//     ll n;
//     cin >> n >> k;
//     // adj.assign(n, {});
//     // deleted.assign(n, 0);
//     // s.resize(n);
//     // ofLength.assign(k + 1, 1e9);
//     ans = 1e9;
//     for (ll i = 0; i < n - 1; i++) {
//         ll a, b, w;
//         cin >> a >> b >> w;
//         adj[a].push_back({b, w});
//         adj[b].push_back({a, w});
//     }
//     divide();
//     cout << (ans == 1e9 ? -1 : ans) << '\n';
// }

int best_path(int N, int K, int H[][2], int L[]) {
    ll i;
    k = K;
    // deleted.assign(N, 0);
    // adj.assign(N, {});
    // s.resize(N);
    // ofLength.assign(K + 1, 1e9);
    ans = 1e9;
    for (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]});
    }
    divide();
    return (ans == 1e9 ? -1 : ans);
}

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