Submission #1255219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255219		giorgi123glm	Race (IOI11_race)	C++20	21 / 100	3100 ms	110364 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);
    int ans = 2e9;
    function <void(int)> f = [&](int stp) {
        map <int, int> down_sum;
        map <int, int> scr;

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

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

        int centr = stp;
        for (auto [a, b] : scr)
            if (b < scr[centr])
                centr = a;

        dis[centr] = 1;

        map <int, int> can;
        int cnt1 = 0;
        function <void(int,int,int,int,bool)> dfs3 = [&](int p, int par, int dep, int leng, bool save) {
            if (save) {
                if (can[leng] == 0)
                    can[leng] = dep;
                else
                    can[leng] = min (can[leng], dep);
            } else {
                if (can[K - leng] > 0)
                    ans = min (ans, can[K - leng] + dep);

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

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

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

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

    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