Submission #419840

#	Time	Username	Problem	Language	Result	Execution time	Memory
419840		dxz05	Race (IOI11_race)	C++14	100 / 100	723 ms	31788 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], P[MAXN];

void dfs(int v, int p, int dist, int cnt, vector<pair<int,int> > &dists) {
    dists.push_back({dist,cnt});
    //cout <<v << endl;
    for (auto [x,y]:g[v]) {
        if (x!=p && D[x] ==-1)  {
//            cout <<"\t" << x << endl;

            dfs(x,v, dist +y,cnt+1, dists);
        }
    }
}

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);
void build_centroid_tree(int v, int p, int dep, int n){

    int centroid = -1;
    get_centroid(v, -1, n, centroid);
    if (centroid == -1) centroid = v;

    D[centroid] = dep;
    P[centroid] = p;
//    cout <<"centroid = " << centroid << " depth = " << dep << endl;

    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;
  //      cout <<"pre dfs" << endl;
        dfs(u, v, w, 1, dists);
    //    cout << "post dfs" << endl;
        for (auto &now : dists){
            int x = now.first, cnt = now.second;

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

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


    }

    for (auto x:changed) d[x] = -1;

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


}

int best_path(int N, int K, int H[][2], int L[]){
    k = K;
    d[0] = 0;
    fill(D,D+MAXN,-1);

    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(0, -1, 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 'void dfs(int, int, int, int, std::vector<std::pair<int, int> >&)':
race.cpp:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto [x,y]:g[v]) {
      |               ^
race.cpp: In function 'int get_centroid(int, int, int, int&)':
race.cpp:30:29: warning: unused variable 'w' [-Wunused-variable]
   30 |         int u = edge.first, w = edge.second;
      |                             ^
race.cpp: In function 'void build_centroid_tree(int, int, int, int)':
race.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             if (x >= d.size()) continue;
      |                 ~~^~~~~~~~~~~
race.cpp:87:29: warning: unused variable 'w' [-Wunused-variable]
   87 |         int u = edge.first, w = edge.second;
      |                             ^

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