Submission #419048

#	Time	Username	Problem	Language	Result	Execution time	Memory
419048		dxz05	Race (IOI11_race)	C++14	21 / 100	3067 ms	39844 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<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;

    map<int, int> mp;
    mp[0] = 0;


    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 d = now.first, edges = now.second;
            if (mp.find(k - d) != mp.end()){
                ans = min(ans, edges + mp[k - d]);
            }
        }

        for (auto now : res){
            int d = now.first, edges = now.second;
            if (mp.find(d) == mp.end()) mp[d] = edges; else
                mp[d] = min(mp[d], edges);
        }

    }

    vector<pair<int, int>> vec;
    for (auto now : mp){
        vec.emplace_back(now.first + dist, now.second + 1);
    }

    return vec;
}

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

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

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