Submission #419834

#	Time	Username	Problem	Language	Result	Execution time	Memory
419834		dxz05	Race (IOI11_race)	C++14	Compilation error	0 ms	0 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];

int dfs(int v, int p, int dist, int cnt, vector<pair<int,int> > &dists) {
    dists.push_back({dist,cnt});
    for (auto [x,y]:g[v]) {
        if (x!=p&&D[x]!=-1)  {
            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 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<int> dists;
        dfs(u, v, w, 1, dists);
        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 || d[x] > cnt) {
                changed.push_back(x);
                d[x] = cnt;
            }
        }


    }

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

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


    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 dfs(int, int, int, int, std::vector<std::pair<int, int> >&)':
race.cpp:17:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for (auto [x,y]:g[v]) {
      |               ^
race.cpp:22:1: warning: no return statement in function returning non-void [-Wreturn-type]
   22 | }
      | ^
race.cpp: In function 'int get_centroid(int, int, int, int&)':
race.cpp:27:29: warning: unused variable 'w' [-Wunused-variable]
   27 |         int u = edge.first, w = edge.second;
      |                             ^
race.cpp: In function 'void build_centroid_tree(int, int, int, int, int)':
race.cpp:54:25: error: invalid initialization of reference of type 'std::vector<std::pair<int, int> >&' from expression of type 'std::vector<int>'
   54 |         dfs(u, v, w, 1, dists);
      |                         ^~~~~
race.cpp:15:66: note: in passing argument 5 of 'int dfs(int, int, int, int, std::vector<std::pair<int, int> >&)'
   15 | int dfs(int v, int p, int dist, int cnt, vector<pair<int,int> > &dists) {
      |                                          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
race.cpp:56:25: error: request for member 'first' in 'now', which is of non-class type 'int'
   56 |             int x = now.first, cnt = now.second;
      |                         ^~~~~
race.cpp:59:43: error: 'cnt' was not declared in this scope; did you mean 'int'?
   59 |                 ans = min(ans, d[k - x] + cnt);
      |                                           ^~~
      |                                           int
race.cpp:64:25: error: request for member 'first' in 'now', which is of non-class type 'int'
   64 |             int x = now.first, cnt = now.second;
      |                         ^~~~~
race.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if (x >= d.size()) continue;
      |                 ~~^~~~~~~~~~~
race.cpp:66:38: error: 'cnt' was not declared in this scope; did you mean 'int'?
   66 |             if (d[x] == -1 || d[x] > cnt) {
      |                                      ^~~
      |                                      int
race.cpp:83:12: error: 'vec' was not declared in this scope
   83 |     return vec;
      |            ^~~