Submission #1255235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255235		giorgi123glm	Race (IOI11_race)	C++20	21 / 100	3101 ms	184152 KiB

race

#include "race.h"
#include <functional>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int best_path(int N, int K, int H[][2], int L[]) {
    vector <vector <pair <int, int> > > gr (N); 
    
    for (int i = 0; i < N - 1; i++) {
        gr[H[i][0]].emplace_back (H[i][1], L[i]);
        gr[H[i][1]].emplace_back (H[i][0], L[i]);
    }

    vector <bool> dis (N + 1);
    vector <int> down_sum (N + 1);
    vector <int> scr (N + 1);
    vector <pair <int, int> > can (K + 1, {0, -1});
    int ans = 2e9;
    auto f = [&](auto& f, int stp)->void {
        vector <int> points;

        auto dfs1 = [&](auto& dfs1, int p, int par)->void {
            down_sum[p] = 1;
            points.emplace_back (p);
            for (pair <int, int>& e : gr[p])
                if (e.first != par && !dis[e.first]) {
                    dfs1 (dfs1, e.first, p);
                    down_sum[p] += down_sum[e.first];
                }
        };
        dfs1 (dfs1, stp, -1);

        auto dfs2 = [&](auto& dfs2, int p, int par)->void {
            scr[p] = max (scr[p], (int)points.size() - down_sum[p]);
            for (pair <int, int>& e : gr[p])
                if (e.first != par && !dis[e.first]) {
                    dfs2 (dfs2, e.first, p);
                    scr[p] = max (scr[p], down_sum[e.first]);
                }
        };
        dfs2 (dfs2, stp, -1);

        int centr = stp;
        for (auto e : points)
            if (scr[e] < scr[centr])
                centr = e;

        dis[centr] = 1;

        bool save = 0;
        int leng = 0;
        int dep = 0;
        auto dfs3 = [&](auto& dfs3, int p, int par)->void {
            if (leng > K)
                return;

            if (save) {
                if (can[leng].second != stp)
                    can[leng] = {dep, stp};
                else {
                    can[leng].first = min (can[leng].first, dep);
                }
            } else {
                if (can[K - leng].second == stp)
                    ans = min (ans, can[K - leng].first + dep);

                if (leng == K)
                    ans = min (ans, dep);
            }

            for (pair <int, int>& e : gr[p])
                if (e.first != par && !dis[e.first]) {
                    dep++;
                    leng += e.second;
                    dfs3 (dfs3, e.first, p);
                    dep--;
                    leng -= e.second;
                }
        };

        for (pair <int, int>& e : gr[centr])
            if (!dis[e.first]) {
                leng = e.second;
                dep = 1;
                save = 0;
                dfs3 (dfs3, e.first, centr);
                leng = e.second;
                dep = 1;
                save = 1;
                dfs3 (dfs3, e.first, centr);
            }

        for (pair <int, int>& e : gr[centr])
            if (!dis[e.first])
                f (f, e.first);
    };

    f (f, 0);

    if (ans == 2e9)
        return -1;
    return ans;
}

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