Submission #391702

#	Time	Username	Problem	Language	Result	Execution time	Memory
391702		ntabc05101	Race (IOI11_race)	C++14	0 / 100	6 ms	8908 KiB

race

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

#define LL long long
#define f first
#define s second

const int mxN = 200000;
const int mxK = 1000000;

int n, k;
vector< pair<int, int> > adj[mxN + 5];
int n_child[mxN + 5];
int cnt[mxK + 5]{1};
bool used[mxN + 5];
int mx_depth;
int result;

int get_subtree_size(int u, int p = -1) {
        n_child[u] = 1;
        for (auto& to: adj[u]) {
                if (!used[to.f] && to.f != p) {
                        n_child[u] += get_subtree_size(to.f, u);
                }
        }

        return n_child[u];
}

int get_centroid(int desired, int u, int p = -1) {
        for (auto& to: adj[u]) {
                if (!used[to.f] && to.f != p && n_child[to.f] >= desired) {
                        return get_centroid(desired, to.f, u);
                }
        }

        return u;
}

void get_cnt(int u, int p, bool e, int w, int depth) {
        if (w > k) {
                return ;
        }

        mx_depth = max(mx_depth, depth);
        if (e) {
                cnt[w] = min(cnt[w], depth);
        }
        else {
                result = min(result, cnt[k - w] + depth);
        }

        for (auto& to: adj[u]) {
                if (!used[to.f] && to.f != p) {
                        get_cnt(to.f, u, e, w + to.s, depth + 1);
                }
        }
}

void centroid_decomp(int u) {
        int centroid = get_centroid(get_subtree_size(u) >> 1, u);
        used[centroid] = true;
        mx_depth = 0;

        for (auto& to: adj[centroid]) {
                if (!used[to.f]) {
                        get_cnt(to.f, centroid, false, to.s, 1);
                        get_cnt(to.f, centroid, true, to.s, 1);
                }
        }

        fill(cnt + 1, cnt + mx_depth + 1, 0);
        for (auto& to: adj[centroid]) {
                if (!used[to.f]) {
                        centroid_decomp(to.f);
                }
        }
}

int best_path(int N, int K, int H[][2], int L[]) {
        n = N, k = K;
        for (int i = 0; i < n - 1; i++) {
                //H[i][0]--, H[i][1]--;

                adj[H[i][0]].emplace_back(H[i][1], L[i]);
                adj[H[i][1]].emplace_back(H[i][0], L[0]);
        }

        cnt[0] = 0;
        for (int i = 1; i <= mxK; i++) {
                cnt[i] = n;
        }
        result = n;

        centroid_decomp(0);

        return (result == n ? -1: result);
}

/*int main() {
        cin.tie(0)->sync_with_stdio(0);
        
        int N, K; cin >> N >> K;
        int H[N][2], L[N];
        for (int i = 0, x, y; i < N - 1; i++) {
                cin >> H[i][0] >> H[i][1] >> L[i];
        }
        
        cout << best_path(N, K, H, L) << endl;

        return 0;
}*/

/*
4 3
0 1 1
1 2 2
1 3 4

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/

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