Submission #341323

#	Time	Username	Problem	Language	Result	Execution time	Memory
341323		Aldas25	Race (IOI11_race)	C++14	21 / 100	3064 ms	20588 KiB

race

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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define pb push_back
#define f first
#define s second
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 200100, MAXK = 21;

int n, k;
vector<pii> adj[MAXN];
ll pref[MAXN];
int par[MAXN][MAXK];
int dep[MAXN];

void dfs1 (int v, int p) {
    FOR(i, 1, MAXK-1) {
        par[v][i] = par[par[v][i-1]][i-1];
    }

    for(auto pp : adj[v]) {
        int u = pp.f;
        ll w = pp.s;
        if (u == p) continue;
        pref[u] = pref[v] + w;
        par[u][0] = v;
        dep[u] = dep[v]+1;
        dfs1 (u, v);
    }
}

int lca (int u, int v) {
    if (u == v) return u;
    if (dep[u] > dep[v]) swap(u,v);
    int d = dep[v] - dep[u];
    FOR(i, 0, MAXK-1)
        if (d & (1<<i))
            v = par[v][i];
    if (u == v) return u;
    for (int i = MAXK-1; i >= 0; i--) {
        if (par[v][i] != par[u][i]) {
            v = par[v][i];
            u = par[u][i];
        }
    }
    return par[u][0];
}

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

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

int sub2 () {
    dfs1 (1, -1);

    int ans = -1;
    FOR(i, 1, n) FOR(j, 1, n) {
        if (d(i,j) == k) {
            int cur = d2(i,j);
            if (ans == -1) ans = cur;
            else ans = min(ans, cur);
        }
    }

    return ans;
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;
    FOR(i, 0, n-2) {
        int u = H[i][0], v = H[i][1], w = L[i];
        u++;
        v++;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }

    if (N <= 1000)
        return sub2();
    else
        return sub2();
}

/*
input 1
4 3
0 1 1
1 2 2
1 3 4
2

input 2
3 3
0 1 1
1 2 1
-1

input 3
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2



*/

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