Submission #419855

#	Time	Username	Problem	Language	Result	Execution time	Memory
419855		dxz05	Race (IOI11_race)	C++14	100 / 100	640 ms	34908 KiB

race

#pragma GCC optimize("Ofast")
#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];

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;
}

void dfs(int v, int p, int dist, int cnt, vector<pair<int, int>> &dists){
    dists.emplace_back(dist, cnt);
    for (auto edge : g[v]){
        int u = edge.first, w = edge.second;
        if (u != p && D[u] == -1){
            dfs(u, v, dist + w, cnt + 1, dists);
        }
    }
}

int ans = 1e9;

int d[2000000];

void build(int v, int dep, int n){
    int centroid = -1;
    get_centroid(v, -1, n, centroid);
    if (centroid == -1) centroid = v;

    D[centroid] = dep;

    vector<int> changed;

    for (auto edge : g[centroid]){
        int u = edge.first, w = edge.second;
        if (D[u] != -1) continue;
        vector<pair<int, int>> dists;
        dfs(u, -1, w, 1, dists);

        for (auto now : dists){
            int x = now.first, cnt = now.second;
            if (x > k) continue;
            if (d[k - x] != -1){
                ans = min(ans, cnt + d[k - x]);
            }
        }

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

    }

    for (int x : changed){
        d[x] = -1;
    }
    d[0] = 0;

    for (auto edge : g[centroid]){
        int u = edge.first;
        if (D[u] == -1) build(u, dep + 1, (n + 1) / 2);
    }

}

int best_path(int N, int K, int H[][2], int L[]){
    k = K;
    fill(D, D + MAXN, -1);
    fill(d, d + 2000000, -1);
    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(0, 1, 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:18:29: warning: unused variable 'w' [-Wunused-variable]
   18 |         int u = edge.first, w = edge.second;
      |                             ^

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