Submission #930586

#	Time	Username	Problem	Language	Result	Execution time	Memory
930586		AtabayRajabli	Race (IOI11_race)	C++17	21 / 100	25 ms	9812 KiB

race

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

#define pb push_back

const int sz = 1e3 + 5;
int t;
int dp[15][sz], in[sz], out[sz], d[sz], e[sz];
vector<array<int, 2>> g[sz];

void dfs(int v, int p)
{
    dp[0][v] = p;
    in[v] = ++t;
    for(auto i : g[v])
    {
        if(i[0] == p)continue;
        d[i[0]] = d[v] + i[1];
        e[i[0]] = e[v] + 1;
        dfs(i[0], v);
    }
    out[v] = ++t;
}

bool anc(int u, int v)
{
    return in[u] <= in[v] && out[v] <= out[u];
}

int lca(int u, int v)
{
    if(anc(u, v))return u;
    if(anc(v, u))return v;
    for(int i = 10; i >= 0; i--)
    {
        if(anc(dp[i][v], u))continue;
        v = dp[i][v];
    }
    return dp[0][v];
}

int dist(int u, int v)
{
    return d[u] + d[v] - d[lca(u, v)] * 2;
}

int len(int u, int v)
{
    return e[u] + e[v] - e[lca(u, v)] * 2;
}

int best_path(int n, int k, int h[][2], int l[])
{
    for(int i = 0; i < n; i++)
    {
        int u = ++h[i][0], v = ++h[i][1], w = l[i];
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    dfs(1, 0);

    for(int i = 1; i <= 10; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][dp[i - 1][j]];
        }
    }

    int mn = 1e9 + 10;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            if(dist(i, j) != k)continue;
            mn = min(mn, len(i, j));
        }
    }
    if(mn == 1e9 + 10)mn = -1;
    return mn;
}

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