Submission #391747

#	Time	Username	Problem	Language	Result	Execution time	Memory
391747		ntabc05101	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

//#include "race.h"
#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];
bool used[mxN + 5];
vector<int> order;
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 ;
        }

        order.push_back(w);
        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);
                }
        }

        for (auto& v: order) {
                cnt[v] = n + 5;
        }
        order.clear();

        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[i]);
        }

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

        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
*/

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:111:25: warning: unused variable 'x' [-Wunused-variable]
  111 |         for (int i = 0, x, y; i < N - 1; i++) {
      |                         ^
race.cpp:111:28: warning: unused variable 'y' [-Wunused-variable]
  111 |         for (int i = 0, x, y; i < N - 1; i++) {
      |                            ^
/tmp/cc1FEiO8.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cccfBsNB.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status