Submission #494505

#	Time	Username	Problem	Language	Result	Execution time	Memory
494505		Alexandruabcde	Race (IOI11_race)	C++14	43 / 100	3042 ms	33352 KiB

race

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

using namespace std;

constexpr int NMAX = 2e5 + 5;
constexpr int VALMAX = 1e6 + 5;
constexpr int INF = 1e9;

typedef pair <int, int> PII;

int ans;

vector <PII> G[NMAX];
int Dist;

int Sz[NMAX];
bool sel[NMAX];

int cnt = 0;
PII fr[VALMAX];

void AddToSolution (int Node, int dad, int cost, int Length) {
    if (cost > Dist) return;

    int remain = Dist - cost;
    if (fr[remain].first == cnt)
        ans = min(ans, fr[remain].second + Length);

    for (auto it : G[Node]) {
        int to = it.first;
        int c = it.second;

        if (to == dad || sel[to]) continue;

        AddToSolution(to, Node, cost + c, Length+1);
    }
}

void ChangeFR (int Node, int dad, int cost, int Length) {
    if (cost > Dist) return;

    if (fr[cost].first == cnt)
        fr[cost].second = min(fr[cost].second, Length);
    else {
        fr[cost].first = cnt;
        fr[cost].second = Length;
    }

    for (auto it : G[Node]) {
        int to = it.first;
        int c = it.second;

        if (to == dad || sel[to]) continue;

        ChangeFR(to, Node, cost + c, Length+1);
    }
}

void Dfs (int Node, int dad = -1) {
    Sz[Node] = 1;

    for (auto it : G[Node]) {
        int to = it.first;

        if (to == dad || sel[to]) continue;

        Dfs(to, Node);
        Sz[Node] += Sz[to];
    }
}

int Size;
int centr;

int Centroid (int Node, int dad = -1) {
    int Max = Size - Sz[Node];

    for (auto it : G[Node]) {
        int to = it.first;

        if (to == dad || sel[to]) continue;

        int x = Centroid(to, Node);
        if (x != -1) return x;

        Max = max(Max, Sz[to]);
    }

    if (Max <= (Size + 1) / 2) return Node;

    return -1;
}

void Get (int Root) {
    Dfs(Root);
    Size = Sz[Root];
    centr = Centroid(Root);

    sel[centr] = 1;
    ++ cnt;
    fr[0].first = cnt;
    fr[0].second = 0;
    for (auto it : G[centr]) {
        int to = it.first;

        AddToSolution(to, centr, it.second, 1);
        ChangeFR(to, centr, it.second, 1);
    }

    for (auto it : G[centr]) {
        int to = it.first;

        if (sel[to]) continue;

        Get(to);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    ans = INF;
    Dist = K;
    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]});
    }

    Get(0);

    if (ans == INF) return -1;
    else return ans;
}

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