Submission #1271461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271461		KALARRY	Race (IOI11_race)	C++20	100 / 100	865 ms	58968 KiB

race

//chockolateman

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

using namespace std;

const long long INF = 1e15;

int k,s[200005],depth[200005],ans;
long long val[200005];
set<pair<int,int>> adj[200005];
map<int,int> min_d;

void dfs1(int v,int p)
{
    s[v] = 1;
    for(auto e : adj[v])
    {
        int u = e.first;
        if(u != p)
        {
            dfs1(u,v);
            s[v] += s[u];
        }
    }
}

int centroid(int v,int p,int n)
{
    for(auto e : adj[v])
    {
        int u = e.first;
        if(u != p && 2*s[u] > n)
            return centroid(u,v,n);
    }
    return v;
}

void dfs2(int v,int p,int add)
{
    if(add==0)
    {
        if(min_d.find(k - val[v]) != min_d.end())
            ans = min(ans,depth[v] + min_d[k - val[v]]);
    }
    else
    {
        if(min_d.find(val[v]) == min_d.end() || min_d[val[v]] > depth[v])
            min_d[val[v]] = depth[v];
    }
    if(v != p)
    {
        for(auto e : adj[v])
        {
            int u = e.first;
            int w = e.second;
            if(u != p)
            {
                val[u] = val[v] + w;
                depth[u] = depth[v] + 1;
                dfs2(u,v,add);
            }
        }
    }
    else
    {
        for(auto e : adj[v])
        {
            int u = e.first;
            int w = e.second;
            val[u] = val[v] + w;
            depth[u] = depth[v] + 1;
            dfs2(u,v,0);
            dfs2(u,v,1);
        }
    }
}

void solve(int v)
{
    dfs1(v,v);
    int n = s[v];
    int c = centroid(v,v,n);
    depth[c] = 0;
    val[c] = 0;
    dfs2(c,c,1);
    min_d.clear();
    vector<pair<int,int>> temp;
    for(auto e : adj[c])
        temp.push_back(e);
    for(auto e : temp)
    {
        adj[c].erase(e);
        int u = e.first;
        int w = e.second;
        adj[u].erase({c,w});
        solve(u);
    }    
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for(int a,b,w,i = 0 ; i < N-1 ; i++)
    {
        a = H[i][0];
        b = H[i][1];
        a++;
        b++;
        w = L[i];
        adj[a].insert({b,w});
        adj[b].insert({a,w});
    }
    ans = N+1;
    solve(1);
    if(ans==N+1)
        ans = -1;
    return ans;
}

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