Submission #1141388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141388		Ariadna	Race (IOI11_race)	C++20	0 / 100	0 ms	324 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;

vector<ll> dist, depth;
vector<vector<pair<int, ll>>> adj;
vector<map<ll, int>> aristas;

void init(int u, int p) {
    depth[u] = depth[p]+1;
    for (pair<int, ll> v: adj[u]) {
        if (v.fi != p) {
            dist[v.fi] = dist[u]+v.se;
            init(v.fi, u);
        }
    }
    aristas[u][dist[u]] = depth[u];
}

void dfs(int u, int p, int k, ll& ans) {
    for (pair<int, ll> a: adj[u]) {
        int v = a.fi;
        if (v != p) {
            dfs(v, u, k, ans);
            if (aristas[v].size() > aristas[u].size()) swap(aristas[v], aristas[u]);

            for (auto i: aristas[v]) {
                if (aristas[u].find(k+2*dist[u]-i.fi) != aristas[u].end()) {
                    ans = min(ans, i.se+aristas[u][k+2*dist[u]-i.fi]-2*depth[u]);
                }
            }

            for (auto i: aristas[v]) {
                if (aristas[u].find(i.fi) != aristas[u].end()) {
                    aristas[u][i.fi] = min(aristas[u][i.fi], i.se);
                } else {
                    aristas[u][i.fi] = i.se;
                }
            }
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    adj = vector<vector<pair<int, ll>>>(N);
    dist = depth = vector<ll>(N);
    aristas = vector<map<ll, int>>(N);

    for (int i = 0; i < N-1; ++i) {
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }

    dist[0] = 0; depth[0] = -1;
    init(0, 0);

    ll ans = 1e9;
    dfs(0, 0, K, ans);
    return ans;
}

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