Submission #672006

#	Time	Username	Problem	Language	Result	Execution time	Memory
672006		vjudge1	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include "race.h"
#include <bits/stdc++.h>

#define el '\n'

typedef long long ll;
typedef long double ld;

using namespace std;

const int INF = 1e9;

struct Centroid {
    vector<bool> vis;
    map<ll, int> paths;
    vector<int> sz, par;
    vector<pair<ll, int>> dis;
    vector<vector<pair<int, int>>> g;

    Centroid(const vector<vector<pair<int, int>>> &g) : g(g) {
        sz.resize(g.size());
        vis.resize(g.size());
        par.resize(g.size());
    }

    int dfsSz(int u, int p) {
        sz[u] = 1;

        for (auto v: g[u]) {
            if (v.first == p || vis[v.first])
                continue;

            sz[u] += dfsSz(v.first, u);
        }

        return sz[u];
    }

    int dfsCentroid(int u, int p, int n) {
        for (auto v: g[u]) {
            if (v.first == p || vis[v.first])
                continue;

            if (sz[v.first] > n / 2)
                return dfsCentroid(v.first, u, n);
        }

        return u;
    }

    void dfs(int u, int p, int cur, ll curDis) {
        dis.emplace_back(curDis, cur);

        for (auto v: g[u]) {
            if (v.first == p || vis[v.first])
                continue;

            dfs(v.first, u, cur + 1, curDis + v.second);
        }
    }

    int build(int u, int p, int &k) {
        int centroid = dfsCentroid(u, p, dfsSz(u, p));

        if (p == -1)
            p = centroid;

        par[centroid] = p;

        vis[centroid] = 1;

        int ret = INF;

        for (auto v: g[centroid]) {
            if (vis[v.first])
                continue;

            dis.clear();

            dfs(v.first, centroid, 1, v.second);

            for (auto i: dis) {
                if (paths[k - i.first])
                    ret = min(ret, i.second + paths[k - i.first]);
            }

            for (auto i: dis) {
                if (!paths[i.first])
                    paths[i.first] = i.second;

                paths[i.first] = min(paths[i.first], i.second);
            }
        }

        paths.clear();

        for (auto v: g[centroid]) {
            if (vis[v.first])
                continue;

            ret = min(ret, build(v.first, centroid, k));
        }

        return ret;
    }
};

int best_path(int N, int K, int H[][2], int L[])
{
    vector<pair<int, int>> g(N + 1);
    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]);
    }

    Centroid c(g);

    int sol = c.build(1, -1, K);

    return (sol == 1e9 ? -1 : sol);
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:112:20: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'struct std::pair<int, int>'} has no member named 'emplace_back'
  112 |         g[H[i][0]].emplace_back(H[i][1], L[i]);
      |                    ^~~~~~~~~~~~
race.cpp:113:20: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'struct std::pair<int, int>'} has no member named 'emplace_back'
  113 |         g[H[i][1]].emplace_back(H[i][0], L[i]);
      |                    ^~~~~~~~~~~~
race.cpp:116:17: error: no matching function for call to 'Centroid::Centroid(std::vector<std::pair<int, int> >&)'
  116 |     Centroid c(g);
      |                 ^
race.cpp:20:5: note: candidate: 'Centroid::Centroid(const std::vector<std::vector<std::pair<int, int> > >&)'
   20 |     Centroid(const vector<vector<pair<int, int>>> &g) : g(g) {
      |     ^~~~~~~~
race.cpp:20:52: note:   no known conversion for argument 1 from 'std::vector<std::pair<int, int> >' to 'const std::vector<std::vector<std::pair<int, int> > >&'
   20 |     Centroid(const vector<vector<pair<int, int>>> &g) : g(g) {
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
race.cpp:13:8: note: candidate: 'Centroid::Centroid(const Centroid&)'
   13 | struct Centroid {
      |        ^~~~~~~~
race.cpp:13:8: note:   no known conversion for argument 1 from 'std::vector<std::pair<int, int> >' to 'const Centroid&'
race.cpp:13:8: note: candidate: 'Centroid::Centroid(Centroid&&)'
race.cpp:13:8: note:   no known conversion for argument 1 from 'std::vector<std::pair<int, int> >' to 'Centroid&&'