Submission #1131579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131579		Luvidi	Race (IOI11_race)	C++20	100 / 100	704 ms	171120 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

const int maxn=2e5;
vector<pair<long long,int>> adj[maxn];
int ans,dp[maxn],sz[maxn],k;
map<long long,int> m[maxn];
long long ds[maxn];

void dfs1(int v,int p){
    for(auto[u,w]:adj[v])if(u!=p){
        dp[u]=dp[v]+1;
        ds[u]=ds[v]+w;
        dfs1(u,v);
    }
}

void dfs2(int v,int p){
    int x=-1;
    for(auto[u,w]:adj[v])if(u!=p){
        if(x==-1||sz[u]>sz[x])x=u;
    }
    if(x!=-1){
        dfs2(x,v);
        swap(m[v],m[x]);
        for(auto[u,w]:adj[v])if(u!=p&&u!=x){
            dfs2(u,v);
            for(auto[x,y]:m[u]){
                if(m[v].count(k+2*ds[v]-x))ans=min(ans,m[v][k+2*ds[v]-x]+y-2*dp[v]);
            }
            for(auto[x,y]:m[u]){
                if(!m[v].count(x))m[v][x]=y;
                m[v][x]=min(m[v][x],y);
            }
        }
    }
    if(m[v].count(k+ds[v]))ans=min(ans,m[v][k+ds[v]]-dp[v]);
    if(!m[v].count(ds[v]))m[v][ds[v]]=dp[v];
    m[v][ds[v]]=min(m[v][ds[v]],dp[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]});
    }
    ans=1e9;
    dfs1(0,0);
    dfs2(0,0);
    if(ans==1e9)ans=-1;
    return ans;
}

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