Submission #98993

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98993	2019-02-28T02:43:53 Z	Hideo	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

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

using namespace std;

#define mk make_pair
#define pb push_back
#define sc second
#define fr first
#define pii pair < int, int >
#define vii vector < pii >

const int MAXN = 2e5 + 7;
const int MAXK = 1e6 + 7;
const int INF = 1e9 + 7;

int ans = INF, k, t;
int st[MAXK], mt[MAXK], h[MAXN], del[MAXN];

vii g[MAXN];

void dfs (int v, int p = -1){
    h[v] = 1;
    for (pii to : g[v])
        if (to.fr != p && !del[to.fr])
            dfs(to.fr, v);
    if (p != -1)
        h[p] += h[v];
}

int centroid (int v){
    dfs(v);
    bool ok = false;
    int c = v, pr = 0;
    while (ok){
        ok = false;
        for (pii to : g[c]){
            if (to.fr != pr && !del[to.fr] && h[to.fr] * 2 >= h[v]){
                pr = c;
                c = to.fr;
                ok = true;
                break;
            }
        }
    }
    return c;
}

void findAns (int v, int p, int l, int d = 1){
    if (k > l && mt[k - l] == t)
        ans = min(ans, d + st[k - l]);
    else if (k == l)
        ans = min(ans, d);
    if (l > k)
        return;
    for (pii to : g[v])
        if (to.fr != p && !del[to.fr])
            findAns (to.fr, v, l + to.sc, d + 1);
}

void upd (int v, int p, int l, int d = 1){
    if (k > l && mt[l] != t){
        mt[l] = t;
        st[l] = d;
    }
    else if (k > l)
        st[l] = min(d, st[l]);
    else
        return;
    for (pii to : g[v])
        if (to.fr != p && !del[to.fr])
            upd(to.fr, v, l + to.sc, d + 1);
}

void calc (int v = 0){
    v = centroid(v);
    del[v] = 1;
    t++;
    for (pii to : g[v]){
        if (!del[to.fr]){
            findAns(to.fr, v, to.sc);
            upd(to.fr, v, to.sc);
        }
    }
    for (pii to : g[v])
        if (!del[to.fr])
            calc (to.fr);
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for (int i = 0; i < N - 1; i++){
        g[H[i][0]].pb(mk(H[i][1], L[i]));
        g[H[i][1]].pb(mk(H[i][0], L[i]));
    }
    calc();
    if (ans == INF)
        return -1;
    return ans;
}

Compilation message

/tmp/cciQqpnj.o: In function `read_input()':
race.cpp:(.text+0x30): multiple definition of `read_input()'
/tmp/cceAmYkh.o:grader.cpp:(.text+0x0): first defined here
/tmp/cciQqpnj.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cceAmYkh.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status