Submission #717204

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

race

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

#define pii pair<int, int>

using namespace std;

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

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

int timeIn[MAX], timeOut[MAX];
int t = 0;

int par[LOGMAX][MAX];

void dfs1(int node, int p, int h, int d){
    par[0][node] = p;
    height[node] = h;
    dist[node] = d;
    timeIn[node] = ++t;
    for(auto to:g[node]){
        if(to.first == p) continue;
        dfs1(to.first, node, h + 1, d + to.second);
    }
    timeOut[node] = t;
}

bool isAncestor(int u, int v){
    return timeIn[u] <= timeIn[v] && timeOut[u] >= timeOut[v];
}

int lca(int u, int v){
    if(isAncestor(u, v)) return u;
    if(isAncestor(v, u)) return v;

    for(int j = LOGMAX - 1; j >= 0; j--){
        if(!isAncestor(par[j][u], v)){
            u = par[j][u];
        }
    }
    return par[0][u];
}

int k = 0;
set<pii> s;
int ans = MAX;
void dfs2(int node){
    s.insert({dist[node], node});
    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]);
    }
    for(pii to:g[node]){
        if(to.first == par[0][node]) continue;
        dfs2(to.first);
    }
    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);
    for(int j = 1; j < LOGMAX; j++){
        for (int i = 0; i < N; i++)
        {
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    dfs2(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