Submission #1306115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306115		motion	Race (IOI11_race)	C++20	43 / 100	236 ms	94104 KiB

race

#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> g;
vector<map<long long,int>> m;
vector<long long> dist;
vector<int> dis;
int ans=1e9;
long long k;
int n;
void dfs1(int v,int p,int cur=0,int cur2=0)
{
    dist[v]=cur;
    dis[v]=cur2;
    m[v][cur]=cur2;
    for(auto [x,y]:g[v])
    {
        if(x!=p)
        {
            dfs1(x,v,cur+y,cur2+1);
        }
    }
}

void dfs(int v,int p)
{
    for(auto [x,y]:g[v])
    {
        if(x!=p)
        {
            dfs(x,v);
            if(m[v].size()<=m[x].size())
            {
                for(auto [a,b]:m[v])
                {
                    auto it=m[x].find(k-a+2*dist[v]);
                    if(it!=m[x].end())
                    {
                        ans=min(ans,m[x][k-a+2*dist[v]]+b-2*dis[v]);
                    }
                    auto it2=m[x].find(a);
                    if(it2!=m[x].end())
                    {
                        m[x][a]=min(m[x][a],b);
                    }
                    else
                    {
                         m[x][a]=b;
                    }

                }
                swap(m[x],m[v]);
            }
            else
            {
                for(auto [a,b]:m[x])
                {

                    auto it=m[v].find(k-a+2*dist[v]);
                    if(it!=m[v].end())
                    {
                        ans=min(ans,m[v][k-a+2*dist[v]]+b-2*dis[v]);
                    }
                    auto it2=m[v].find(a);
                    if(it2!=m[v].end())
                    {
                        m[v][a]=min(m[v][a],b);
                    }
                    else
                    {
                         m[v][a]=b;
                    }

                }
            }

        }
    }
}
int best_path(int N,int K,int H[][2], int L[])
{
    n=N;
    k=K;
    g=vector<vector<pair<int,int>>>(n);
    m=vector<map<long long,int>>(n);
    dist=vector<long long>(n,0);
    dis=vector<int>(n,0);
    for(int i=0;i<n-1;i++)
    {
        int a=H[i][0],b=H[i][1],c=L[i];
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    dfs1(0,-1);
    dfs(0,-1);
    if(ans==1e9)
    {
        return -1;
    }
    return ans;
}

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