Submission #830616

#	Time	Username	Problem	Language	Result	Execution time	Memory
830616		Johann	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

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

#define ll long long
#define vi vector<ll>
#define pii pair<ll, ll>
#define vpii vector<pii>
#define vvpii vector<vpii>

#define mll map<ll, ll>
#define vmll vector<mll>

void root(vvpii & adj, int v, int p, vi & height, vi & dist) {
    height[v] = height[p] + 1;
    ll u,d;
    for (pii e : adj[v]) {
        tie(u,d) = e;
        if (u == p) continue;
        dist[u] = dist[v] + d;
        root(adj, u, v, height, dist);
    }
}

void InOrUpdate(mll & DV, ll dv, ll hv) {
    if (DV.find(dv) == DV.end()) DV[dv] = hv;
    else DV[dv] = min(DV[dv], hv);
}
void solve(vvpii & adj, int v, vi & dist, vi & height, vmll & distVert, ll & ans, int K) {
    int maxSub = -1;
    for (pii e : adj[v]) {
        ll u = e.first;
        if (height[u] <= height[v]) continue; // parent; // distances können auch null sein...
        solve(adj, u, dist, height, distVert, ans, K);
        if (maxSub == -1 || distVert[maxSub].size() < distVert[u].size()) maxSub = u;
    }
    if (maxSub != -1) { // not a leaf!
        ll k = K + 2 * dist[v];
        swap(distVert[v], distVert[maxSub]);
        for (pii e : adj[v]) {
            ll u = e.first;
            if (height[u] < height[v] && u != maxSub) continue; // parent or maxSubTree
            for (pii bla : distVert[u]) {
                if (distVert[v].find(k - bla.first) != distVert[v].end()) {
                    ans = min(ans, bla.second + distVert[v][k - bla.first] - 2 * height[v]);
                }
            }
            for (pii bla : distVert [u]) InOrUpdate(distVert[v], bla.first, bla.second);
            distVert[u].clear();
        }
    }
    InOrUpdate(distVert[v], dist[v], height[v]);
    if (distVert[v].find(K + dist[v]) != distVert[v].end()) ans = min(ans, distVert[v][K + dist[v]] - height[v]);
    // printf("Vertex: %d\n", v);  for (pii bla : distVert[v]) {  printf("%d - %d\n", bla.first, bla.second);  }  cout << endl;
}

int best_path(int N, int K, int H[][2], int L[]){
    vvpii adj(N);
    for (int i = 0,a,b; i < N-1; ++i) {
        a = H[i][0];
        b = H[i][1];
        adj[a].push_back({b, L[i]});
        adj[b].push_back({a, L[i]});
    }
    vi height(N, 0), dist(N, 0);
    root(adj, 0, 0, height, dist);

    vmll distVert(N); // { dist[v], height[v] } pairs!
    ll ans = INT_MAX;
    solve(adj, 0, dist, height, distVert,ans, K);

    return (ans == INT_MAX) ? -1 : ans;
}

Compilation message (stderr)

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