제출 #1146852

#제출 시각아이디문제언어결과실행 시간메모리
1146852XXBabaProBerkay경주 (Race) (IOI11_race)C++20
컴파일 에러
0 ms0 KiB
#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);
}

컴파일 시 표준 에러 (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]);
      |                                           ^