Submission #717212

#	Time	Username	Problem	Language	Result	Execution time	Memory
717212		TheSahib	Race (IOI11_race)	C++17	0 / 100	3 ms	2668 KiB

race

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

#define ll long long
#define pii pair<ll, ll>

using namespace std;

const int MAXK = 101;
const int MAX = 1e5 + 5;
const int LOGMAX = 19;

vector<pii> g[MAX];
ll dist[MAX];
int height[MAX];


int k = 0;
set<pii> s;

int ans = MAX;
void dfs1(int node, int p, int h, ll d){
    dist[node] = d;
    height[node] = h;

    auto itr = s.lower_bound({dist[node] - k, 0});
    if(itr != s.end() && (itr->first) == (dist[node] - k)){
        ans = min(ans, height[node] - height[itr->second]);
    }

    s.insert({dist[node], node});
    for(pii to:g[node]){
        if(to.first == p) continue;
        dfs1(to.first, node, h + 1, d + to.second);
    }
    s.erase({dist[node], node});
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    for (int i = 0; i < N - 1; i++)
    {
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs1(0, 0, 0, 0);
    if(ans == MAX) return -1;
    else return ans;
}

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