Submission #884249

#	Time	Username	Problem	Language	Result	Execution time	Memory
884249		AlphaMale06	Race (IOI11_race)	C++14	100 / 100	372 ms	86868 KiB

race

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

using namespace std;

#define pb push_back
#define F first
#define S second

const int N = 2e5+3;
int inf=1e9;
vector<pair<int, int>> adj[N];
int d[N];
int c[N];
int x;
int ans=inf;
map<int, int> mapa[N];

void dfs(int v, int p, int dep, int cost){
    c[v]=cost;
    d[v]=dep;
    for(auto to : adj[v]){
        if(to.F!=p){
            dfs(to.F, v, dep+1, cost+to.S);
        }
    }
}

void bst(int v, int p){
    mapa[v][c[v]]=d[v];
    for(auto to : adj[v]){
        if(to.F!=p){
            bst(to.F, v);
            if(mapa[to.F].size()>mapa[v].size())mapa[v].swap(mapa[to.F]);
            for(auto it : mapa[to.F]){
                int wnt=x+2*c[v]-it.F;
                if(mapa[v].count(wnt))ans=min(ans, mapa[v][wnt]+it.S-2*d[v]);
            }
            for(auto it : mapa[to.F]){
                if(mapa[v].count(it.F))mapa[v][it.F]=min(mapa[v][it.F], it.S);
                else mapa[v][it.F]=it.S;
            }
            if(mapa[v].count(x+c[v])){
                ans=min(ans, mapa[v][x+c[v]]-d[v]);
            }
        }
    }
}

int best_path(int n, int k, int h[][2], int l[])
{
    x=k;
    for(int i=0; i< n-1; i++){
        adj[h[i][0]].pb({h[i][1], l[i]});
        adj[h[i][1]].pb({h[i][0], l[i]});
    }
    dfs(0, -1, 0, 0);
    bst(0, -1);
    if(ans==inf)return -1;
    else return ans;
}

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