Submission #1146852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146852		XXBabaProBerkay	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define PB push_back
#define MP make_pair

using ll = long long;
using pi = pair<int, int>;

template<typename T>
using vec = vector<T>;

template<typename T, const unsigned int N>
using arr = array<T, N>;

const int INF = 1e9 + 7;

int n, k, mx = 1e6, ans = INF;
int sz[100005], mn[1000005];
bool dead[100005];
vec<pi> adj[100005];

int pre_dfs(int u, int p)
{
    sz[u] = 1;
    for (auto v : adj[u])
        if (v.F != p && !dead[v.F])
            sz[u] += pre_dfs(v.F, u);
    return sz[u];
}

int find_centroid(int u, int p, int ts)
{
    for (auto v : adj[u])
        if (v.F != p && !dead[v.F] && sz[v.F] * 2 > ts)
            return find_centroid(v.F, u, ts);
    return u;
}

void dfs(int u, int p, int s, int d, bool f)
{
    if (s > k)
        return;
    mx = max(mx, d);
    if (f)
        mn[s] = min(mn[s], d);
    else
        ans = min(ans, mn[k - s] + d);

    for (auto v : adj[u])
        if (v.F != p && !dead[v.F])
            dfs(v.F, u, s + v.S, d + 1, f);
}

void solve(int u)
{
    int c = find_centroid(u, -1, pre_dfs(u, -1));
    dead[c] = 1;

    fill(mn, mn + mx + 1, INF);

    mx = 0;
    for (auto v : adj[c])
        if (!dead[v.F])
        {
            dfs(v.F, c, v.S, 1, 0);
            dfs(v.F, c, v.S, 1, 1);
        }

    for (auto v : adj[c])
        if (!dead[v.F])
            solve(v.F);
}

int best_path(int N, int K, int (*H), int* L)
{
    n = N, k = K;
    for (int i = 0; i < N - 1; i++)
    {
        adj[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
        adj[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
    }

    solve(1);
    return (ans == INF ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int*, int*)':
race.cpp:82:17: error: invalid types 'int[int]' for array subscript
   82 |         adj[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
      |                 ^
race.cpp:82:43: error: invalid types 'int[int]' for array subscript
   82 |         adj[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
      |                                           ^
race.cpp:83:17: error: invalid types 'int[int]' for array subscript
   83 |         adj[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
      |                 ^
race.cpp:83:43: error: invalid types 'int[int]' for array subscript
   83 |         adj[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
      |                                           ^