Submission #1177228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177228		kfhjad	Race (IOI11_race)	C++20	100 / 100	335 ms	101360 KiB

race

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MX = 200001;
vector<pair<int, int>> adj[MX];
map<ll, int> m[MX];
ll distToRoot[MX], edgesToRoot[MX];

ll K;
ll ans = 1E9;

void dfs(int node, int prev)
{
    m[node][distToRoot[node]] = node;

    for (auto& [u, dist] : adj[node])
        if (u != prev)
        {
            distToRoot[u] = distToRoot[node] + dist;
            edgesToRoot[u] = edgesToRoot[node] + 1;
            dfs(u, node);
    
            if (m[node].size() < m[u].size())
                swap(m[node], m[u]);
                        
            for (auto& [len, v] : m[u])
            {
                ll x = K - len + 2 * distToRoot[node];
                if (m[node].count(x))
                    ans = min(ans, edgesToRoot[v] + edgesToRoot[m[node][x]] - 2 * edgesToRoot[node]);
            }
            
            for (auto& [len, v] : m[u])
            {
                if (m[node].count(len))
                    m[node][len] = edgesToRoot[m[node][len]] < edgesToRoot[v] ? m[node][len] : v;
                else
                    m[node][len] = v;
            }
        }
}

int best_path(int N, int k, int H[][2], int L[])
{
    K = k;
    
    for (int i = 0; i < N - 1; ++i)
    {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    
    dfs(0, 0);
    
    return ans == 1E9 ? -1 : ans;
}

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