Submission #418693

#	Time	Username	Problem	Language	Result	Execution time	Memory
418693		snasibov05	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include "race.h"
#include <vector>
#include <map>

using namespace std;

#define oo 1000000000
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second

int ans = oo;
const int nmax = 2e5 + 5;
vector<pii> ed[nmax];
bool used[nmax];
int size[nmax];
vector<pii> v;

void calcSize(int cur, int pr){
    size[cur] = 1;
    for (auto [x, w] : ed[cur]){
        if (used[x] || x == pr) continue;
        calcSize(x, cur);
        size[cur] += size[x];
    }
}

int findCentroid(int cur, int pr, int n){
    for (auto [x, w] : ed[cur]){
        if (used[x] || x == pr) continue;
        if (size[x] > n / 2){
            return findCentroid(x, cur, n);
        }
    }
    return cur;
}

void dfs(int cur, int pr, int k, int d, int l){
    if (d > k) return;
    v.pb({d, l});
    for (auto [x, w] : ed[cur]){
        if (x == pr || used[x]) continue;
        dfs(x, cur, k, d + w, l + 1);
    }
}

void calc(int cur, int k){
    calcSize(cur, -1);
    cur = findCentroid(cur, -1, size[cur]);

    map<int, int> dp;
    used[cur] = true;

    for (auto [x, w] : ed[cur]){
        v.clear();
        dfs(x, cur, k, w, 1);

        for (auto [d, l] : v){
            if (d == k) ans = min(ans, l);
            if (dp.count(k-d) == 0) continue;
            ans = min(ans, l + dp[k - d]);
        }
        for (auto [d, l] : v){
            if (dp[d] == 0) dp[d] = l;
            else dp[d] = min(dp[d], l);
        }
    }

    for (auto [x, w] : ed[cur]){
        if (used[x]) continue;
        calc(x, k);
    }
}

int best_path(int n, int k, int h[][2], int l[]){
    ed.resize(n);
    used.resize(n);
    size.resize(n);

    for (int i = 0; i < n - 1; ++i) {
        ed[h[i][0]].pb({h[i][1], l[i]});
        ed[h[i][1]].pb({h[i][0], l[i]});
    }

    calc(0, k);

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

    return ans;

}

Compilation message (stderr)

race.cpp: In function 'void calcSize(int, int)':
race.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for (auto [x, w] : ed[cur]){
      |               ^
race.cpp: In function 'int findCentroid(int, int, int)':
race.cpp:30:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for (auto [x, w] : ed[cur]){
      |               ^
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for (auto [x, w] : ed[cur]){
      |               ^
race.cpp: In function 'void calc(int, int)':
race.cpp:55:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for (auto [x, w] : ed[cur]){
      |               ^
race.cpp:59:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for (auto [d, l] : v){
      |                   ^
race.cpp:64:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         for (auto [d, l] : v){
      |                   ^
race.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for (auto [x, w] : ed[cur]){
      |               ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:77:8: error: request for member 'resize' in 'ed', which is of non-class type 'std::vector<std::pair<int, int> > [200005]'
   77 |     ed.resize(n);
      |        ^~~~~~
race.cpp:78:10: error: request for member 'resize' in 'used', which is of non-class type 'bool [200005]'
   78 |     used.resize(n);
      |          ^~~~~~
race.cpp:79:10: error: request for member 'resize' in 'size', which is of non-class type 'int [200005]'
   79 |     size.resize(n);
      |          ^~~~~~