Submission #494497

#	Time	Username	Problem	Language	Result	Execution time	Memory
494497		Alexandruabcde	Race (IOI11_race)	C++14	0 / 100	7 ms	14340 KiB

race

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

using namespace std;

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

typedef long long LL;
typedef pair <int, LL> PIL;

int Dist;

int ans;
map <LL, int> mp[NMAX];
vector <PIL > G[NMAX];

void Dfs (int Node, int dad = -1) {
    mp[Node][0] = 1;
    for (auto it : G[Node]) {
        int to = it.first;
        LL cost = it.second;
        if (to == dad) continue;

        Dfs(to, Node);

        if (mp[to].size() > mp[Node].size())
            swap(mp[to], mp[Node]);

        for (auto drum : mp[to]) {
            LL remain = Dist - drum.first - cost;

            if (mp[Node][remain] != 0)
                ans = min(ans, mp[Node][remain] + drum.second);
        }

        for (auto drum : mp[to]) {
            LL new_drum = drum.first + cost;

            if (new_drum > Dist) continue;

            if (new_drum == Dist) {
                ans = min(ans, drum.second + 1);
                continue;
            }

            if (mp[Node][new_drum] == 0)
                mp[Node][new_drum] = drum.second + 1;
            else mp[Node][new_drum] = min(mp[Node][new_drum], drum.second + 1);
        }
    }
}

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]});
    }

    Dfs(0);

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

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