Submission #1177202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177202		kfhjad	Race (IOI11_race)	C++20	0 / 100	6 ms	14400 KiB

race

#include "race.h"

#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 extra[MX];
int K;
int ans = 1E9;

void merge(int node, int u, int dist)
{
    if (m[node].size() < m[u].size())
    {
        swap(m[node], m[u]);
        swap(extra[node], extra[u]);
        
        
        for (auto& [len, highways] : m[u])
        {
            int x = K - dist - (len + extra[u]) - extra[node];
            if (m[node].count(x))
                ans = min(ans, m[node][x] + highways + 1);
        }
        m[node][-extra[node]] = 1;
        
        if (m[u].count(K - dist - extra[u]))
            ans = min(ans, m[u][K - dist - extra[u]] + 1);

        for (auto& [len, highways] : m[u])
        {
            int x = len + extra[u] - extra[node];
            if (m[node].count(x))
                m[node][x] = min(m[node][x], highways);
            else
                m[node][x] = highways;
        }
        
        extra[node] += dist;
    }
    else
    {
        // if (node == 0 && u == 6)
            // cout << "HI\n";
        m[u][-extra[u]] = 1; // adding u node
        for (auto& [len, highways] : m[u])
        {
            int x = K - dist - (len + extra[u]) - extra[node];
            if (m[node].count(x))
                ans = min(ans, m[node][x] + highways + 1);
            // if (node == 0 && u == 6 && ans == 1)
                // cout << len + extra[u] << " " << m[node][x] << " " << highways << endl;
        }
        
        for (auto& [len, highways] : m[u])
        {
            int x = len + extra[u] + dist - extra[node];
            if (m[node].count(x))
                m[node][x] = min(m[node][x], highways + 1);
            else
                m[node][x] = highways + 1;
        }
    }
}

void dfs(int node, int prev)
{
    for (auto& [u, dist] : adj[node])
    {
        if (u != prev)
        {
            dfs(u, node);
            merge(node, u, dist);
            // if (ans == 1)
            // {
                // cout << node << " " << u << endl;
            // }
        }
    }
    
    if (m[node].count(K - extra[node]))
        ans = min(ans, m[node][K - extra[node]]);
}

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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57