Submission #1292626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292626		newsboy	경주 (Race) (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;

struct CD {
    int n;
    vector<int> siz, dep, parent, area;
    vector<vector<int>> adj, lvl;
    CD() {}
    CD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n);
        dep.assign(n, -1);
        parent.resize(n);
        adj.assign(n, {});
        area.resize(n);
        lvl.clear();
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void build(int u, int p = -1) {
        siz[u] = 1;
        for (auto v : adj[u]) {
            if (v == p) {
                continue;
            }
            if (dep[v] == -1) {
                build(v, u);
                siz[u] += siz[v];
            }
        }
    }
    int find(int u, int p, int tot) {
        for (auto v : adj[u]) {
            if (v == p) {
                continue;
            }
            if (dep[v] == -1 && siz[v] * 2 > tot) {
                return find(v, u, tot);
            }
        }
        return u;
    }
    void work(int u = 0, int p = -1, int cur = 0) {
        build(u);
        int x = find(u, -1, siz[u]);
        dep[x] = cur;
        parent[x] = p;
        if (lvl.size() == cur) {
            lvl.push_back({});
        }
        lvl[cur].push_back(x);
        area[x] = siz[u];
        for (auto y : adj[x]) {
            if (dep[y] == -1) {
                work(y, x, cur + 1);
            }
        }
    }
};

constexpr int inf = 1E9;
constexpr int K = 1E6;
vector<int> f(K + 1, inf);

int best_path(int n, int k, int edges[][2], vector<int> t[]) {
    f[0] = 0;
    CD c(n);
    vector<vector<array<int, 2>>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int u = edges[i][0], v = edges[i][1];
        int w = t[i];
        c.addEdge(u, v);
        adj[u].push_back(array<int, 2>{v, w});
        adj[v].push_back(array<int, 2>{u, w});
    }
    c.work();
    int ans = inf;
    for (int i = 0; i < c.lvl.size(); i++) {
        for (auto x : c.lvl[i]) {
            int need = c.dep[x];
            vector<int> tot;
            for (auto [y, w] : adj[x]) {
                if (c.dep[y] < need) {
                    continue;
                }
                vector<array<int, 2>> cur;
                auto dfs = [&](auto& self, int u, int p, int dis, int dep) -> void {
                    if (dis > k) {
                        return;
                    }
                    cur.push_back(array<int, 2>{dis, dep});
                    for (auto [v, w] : adj[u]) {
                        if (v == p) {
                            continue;
                        }
                        if (c.dep[v] > need) {
                            self(self, v, u, dis + w, dep + 1);
                        }
                    }
                    };
                dfs(dfs, y, x, w, 1);
                for (auto [dis, dep] : cur) {
                    ans = std::min(ans, f[k - dis] + dep);
                    if (f[dis] == inf) {
                        tot.push_back(dis);
                    }
                    f[dis] = std::min(f[dis], dep);
                }
            }
            for (auto x : tot) {
                f[x] = inf;
            }
        }
    }
    if (ans == inf) {
        ans = -1;
    }
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], std::vector<int>*)':
race.cpp:79:20: error: cannot convert 'std::vector<int>' to 'int' in initialization
   79 |         int w = t[i];
      |                 ~~~^
      |                    |
      |                    std::vector<int>