Submission #416937

#	Time	Username	Problem	Language	Result	Execution time	Memory
416937		Emin2004	Race (IOI11_race)	C++14	21 / 100	35 ms	4892 KiB

race

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

#define ll long long
#define pb push_back
#define pii pair<int, ll>
#define F first
#define S second

const int N = 10005;
const int mod = 1e9+7;

int par[1005][20], hgh[N], tin[N], tout[N], tmr = 1;
ll dis[N];
vector<pii> a[N];

void DFS(int node){
    for(int i = 1; i <= 10; i++){
        par[node][i] = par[par[node][i - 1]][i - 1];
    }
    tin[node] = tmr;
    tmr++;
    for(pii i : a[node]){
        if(i.F != par[node][0]){
            par[i.F][0] = node;
            dis[i.F] = dis[node] + i.S;
            hgh[i.F] = hgh[node] + 1;
            DFS(i.F);
        }
    }
    tout[node] = tmr;
    tmr++;
}

bool ispar(int a, int b){
    if(tin[a] < tin[b] && tout[b] < tout[a]) return true;
    return false;
}

int LCA(int a, int b){
    if(ispar(a, b)) return a;
    if(ispar(b, a)) return b;
    if(hgh[a] < hgh[b]) swap(a, b);
    for(int i = 10; i >= 0; i--){
        if(par[a][i] == -1) continue;
        if(!ispar(par[a][i], b)) a = par[a][i];
    }
    return par[a][0];
}

int best_path(int n, int k, int h[][2], int l[]){
    for(int i = 0; i < n - 1; i++){
        int u = h[i][0];
        int v = h[i][1];
        a[u].pb({v, l[i]});
        a[v].pb({u, l[i]});
        for(int j = 0; j < 11; j++) par[i][j] = -1;
    }
    for(int j = 0; j < 11; j++) par[n - 1][j] = -1;
    DFS(0);
    int ans = n + 5;
    for(int i = 0; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            int anc = LCA(i, j);
            ll lnt = dis[i] + dis[j] - dis[anc] - dis[anc];
            if(lnt == k){
                ans = min(ans, hgh[i] + hgh[j] - hgh[anc] - hgh[anc]);
            }
        }
    }
    if(ans == n + 5) return -1;
    return ans;
}

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