Submission #866452

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

race

#include "file.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back
#define mt make_tuple

#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(x) (int)x.size()
#define uniq(x) unique(all(x)), x.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

struct Graph {
    int n, k;
    int tot = 2e9;
    map <int, int> H;
    vt <ar <int, 2>> paths;
    vt <vt <ar <int, 2>>> adj;

    Graph(int n, int k): n(n), k(k) {
        H.clear();
        paths.clear();
        adj.assign(n, vt <ar <int, 2>>());
    }

    void add_edge(int u, int v, int w) {
        adj[u].pub({v, w});
        adj[v].pub({u, w});
    }

    void dfs(int u, int p, int c, int lvl = 1) {
        if (c > k) {
            return; 
        }     
        paths.pub({c, lvl});
        for (auto& [v, w] : adj[u]) {
            if (v == p || rem[v]) 
                continue;
            dfs(v, u, c + w, lvl + 1);
        }
    }

    //Centroid Decomposition
    vt <bool> rem;
    vt <int> par, sz;

    void initCD() {
        sz.resize(n);
        rem.resize(n);
        par.resize(n);
        build(0, -1);
    }

    void build(int u, int p) {
        int n = dfsC(u, p);
        int centroid = get_centroid(u, p, n);
        
        par[centroid] = p;
        rem[centroid] = true;

        H.clear();
        H[0] = 0;
        for (auto& [v, w] : adj[centroid]) {
            if (rem[v]) {
                continue;
            }

            paths.clear();
            dfs(v, centroid, w);
            for (auto& [path, nr] : paths) {
                if (H.count(k - path))
                  tot = min(tot, H[k - path] + nr);
            }

            for (auto& [path, nr] : paths) {
                if (H.count(path)) H[path] = min(H[path], nr);
                else H[path] = nr;
            }
        }

        for (auto& [v, w] : adj[centroid]) {
            if (rem[v]) {
                continue;
            }
            build(v, centroid);
        }
    }

    int dfsC(int u, int p) {
        sz[u] = 1;
        for (auto& [v, w] : adj[u]) {
            if (v == p || rem[v])
                continue;
            dfsC(v, u);
            sz[u] += sz[v];
        }
        return sz[u];
    }

    int get_centroid(int u, int p, int n) {
        for (auto& [v, w] : adj[u]) {
            if (v == p || rem[v])
                continue;
            if (sz[v] * 2 > n)
                return get_centroid(v, u, n);
        }
        return u;
    }
};

int best_path(int N, int K, int H[][2], int L[]) {
    Graph G(N, K);
    for (int i = 0; i < N - 1; ++i) {
      G.add_edge(H[i][0], H[i][1], L[i]);
    }
    G.initCD();
    return G.tot == 2e9? -1 : G.tot;
}

Compilation message (stderr)

race.cpp:1:10: fatal error: file.h: No such file or directory
    1 | #include "file.h"
      |          ^~~~~~~~
compilation terminated.