Submission #419186

#	Time	Username	Problem	Language	Result	Execution time	Memory
419186		dxz05	경주 (Race) (IOI11_race)	C++14	0 / 100	7 ms	9036 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 3e2;

vector<pair<int, int>> g[MAXN];

int k;
int D[MAXN], P[MAXN];

int get_centroid(int v, int p, int n, int &centroid){
    int size = 1;
    for (auto edge : g[v]){
        int u = edge.first, w = edge.second;
        if (D[u] == -1 && u != p){
            size += get_centroid(u, v, n, centroid);
        }
    }

    if (size >= (n + 1) / 2 && centroid == -1) centroid = v;

    return size;
}

int ans = 1e9;
vector<int> d(1000001,-1);
vector<pair<int, int>> build_centroid_tree(int v, int p, int dep, int dist, int n){
    int centroid = -1;
    get_centroid(v, -1, n, centroid);
    if (centroid == -1) centroid = v;

    D[centroid] = dep;
    P[centroid] = p;

    vector<int> changed;

    for (auto edge : g[centroid]){
        int u = edge.first, w = edge.second;
        if (u == p || D[u] == -1) continue;

        vector<pair<int, int>> res = build_centroid_tree(u, centroid, dep + 1, w, (n + 1) / 2);

        //cout << centroid << "->" << u << endl;
        //for (auto now : res) cout << now.first << ' ' << now.second << endl; cout << endl;

        for (auto now : res){
            int x = now.first, cnt = now.second;

            if (k >= x && d[k - x] != -1) {
                ans = min(ans, d[k - x] + cnt);
            }
        }

        for (auto now : res){
            int x = now.first, cnt = now.second;
            if (x >= d.size()) continue;
            if (d[x] == -1 || d[x] > cnt) {
                changed.push_back(x);
                d[x] = cnt;
            }
        }


    }

    vector<pair<int, int>> vec = {make_pair(dist, 1)};
    for (auto x:changed) {
        if (x + dist <= k && d[x] != -1) vec.push_back({x + dist, d[x] + 1});
        d[x] = -1;
    }

    return vec;
}

int best_path(int N, int K, int H[][2], int L[]){
    k = K;
    d[0] = 0;

    for (int i = 0; i < N - 1; i++){
        g[H[i][0]].emplace_back(H[i][1], L[i]);
        g[H[i][1]].emplace_back(H[i][0], L[i]);
    }

    build_centroid_tree(1, -1, 1, 0, N);

    if (ans == 1e9) ans = -1;

    return ans;
}

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

3 3
0 1 1
1 2 1
-1

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
2



*/

Compilation message (stderr)

race.cpp: In function 'int get_centroid(int, int, int, int&)':
race.cpp:16:29: warning: unused variable 'w' [-Wunused-variable]
   16 |         int u = edge.first, w = edge.second;
      |                             ^
race.cpp: In function 'std::vector<std::pair<int, int> > build_centroid_tree(int, int, int, int, int)':
race.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if (x >= d.size()) continue;
      |                 ~~^~~~~~~~~~~

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