Submission #100454

#	Time	Username	Problem	Language	Result	Execution time	Memory
100454		alexpetrescu	Race (IOI11_race)	C++14	100 / 100	2958 ms	87800 KiB

race

#include "race.h"
#include <vector>
#include <map>

#define MAXN 200000

struct myc {int x, y;};
std::map <long long, myc> val;
int timp;
std::vector < myc > g[MAXN];
int s[MAXN], k, h[MAXN];
int fiuMare[MAXN], t[MAXN];
long long u[MAXN];
int ans, cine;
bool tip;

void dfs(int x) {
    s[x] = 1;
    fiuMare[x] = x;
    for (auto &y : g[x]) {
        if (h[y.x] == 0) {
            h[y.x] = h[x] + 1;
            u[y.x] = u[x] + y.y;
            t[y.x] = x;
            dfs(y.x);
            s[x] += s[y.x];
            if (s[y.x] > s[fiuMare[x]] || fiuMare[x] == x)
                fiuMare[x] = y.x;
        }
    }
}

inline void vezi(int x) {
    if (ans == -1 || x < ans)
        ans = x;
}

inline void baga(int x) {
    myc &t = val[u[x]];
    if (t.y != timp || t.x > h[x])
        t = {h[x], timp};
}

void tot(int x) {
    if (tip)
        baga(x);
    else {
        int e = k + 2 * u[cine] - u[x];
        if (e >= 0 && val[e].y == timp)
            vezi(h[x] - 2 * h[cine] + val[e].x);
    }
    for (auto &y : g[x])
        if (t[y.x] == x)
            tot(y.x);
}

inline void solve(int x) {
    bool ok = 1;
    while (ok) {
        for (auto &y : g[x]) {
            if (t[y.x] == x && y.x != fiuMare[x]) {
                cine = x;
                tip = 0;
                tot(y.x);
                tip = 1;
                tot(y.x);
            }
        }
        baga(x);
        int e = u[x] + k;
        if (e >= 0 && val[e].y == timp)
            vezi(val[e].x - h[x]);
        if (t[x] != -1 && fiuMare[t[x]] == x)
            x = t[x];
        else
            ok = 0;
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N - 1; i++)g[H[i][0]].push_back({H[i][1], L[i]}), g[H[i][1]].push_back({H[i][0], L[i]});
    for (int i = 0; i < N; i++)
        h[i] = 0;
    int rad = 0;
    h[rad] = 1;
    u[rad] = 0;
    t[rad] = -1;
    dfs(rad);
    ans = -1;
    k = K;
    for (int i = 0; i < N; i++) {
        if (fiuMare[i] == i) {
            timp++;
            solve(i);
        }
    }
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57