Submission #1210791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210791		Born_To_Laugh	Race (IOI11_race)	C++17	0 / 100	7 ms	14400 KiB

race

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

typedef long long ll;
typedef pair<ll, ll> pii;

#define f first
#define s second

const int maxn = 200001;

vector<pii> adj[maxn];
map<ll, ll> info[maxn];
ll dist[maxn], sum[maxn];
int N;
ll K;
ll ret = LLONG_MAX;

void sack(int u, int p) {
    vector<int> children;
    for (auto &edge : adj[u]) {
        if (edge.f == p) continue;
        children.push_back(edge.f);
    }

    for (int v : children) {
        sack(v, u);
    }

    int largest = -1;
    for (int v : children) {
        if (largest == -1 || info[v].size() > info[largest].size()) {
            largest = v;
        }
    }

    if (largest != -1) {
        swap(info[u], info[largest]);
    }

    if (info[u].find(sum[u]) == info[u].end()) {
        info[u][sum[u]] = dist[u];
    } else {
        info[u][sum[u]] = min(info[u][sum[u]], dist[u]);
    }

    ll target = 2 * sum[u] + K;

    for (int v : children) {
        if (v == largest) continue;
        for (auto &kv : info[v]) {
            ll s_val = kv.f;
            ll d_val = kv.s;
            auto it = info[u].find(target - s_val);
            if (it != info[u].end()) {
                ll candidate = it->s + d_val - 2 * dist[u];
                if (candidate < ret) {
                    ret = candidate;
                }
            }
        }
        for (auto &kv : info[v]) {
            ll s_val = kv.f;
            ll d_val = kv.s;
            auto it = info[u].find(s_val);
            if (it == info[u].end()) {
                info[u][s_val] = d_val;
            } else {
                it->s = min(it->s, d_val);
            }
        }
        info[v].clear();
    }
}

int best_path(int n, int k, int edges[][2], int weights[]) {
    N = n;
    K = k;
    ret = LLONG_MAX;

    for (int i = 0; i < n; i++) {
        adj[i].clear();
        info[i].clear();
    }

    for (int i = 0; i < n-1; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        int w = weights[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<int> parent(n, -1);
    stack<int> st;
    st.push(0);
    dist[0] = 0;
    sum[0] = 0;
    parent[0] = -1;
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        for (auto &edge : adj[u]) {
            int v = edge.f;
            ll w = edge.s;
            if (v == parent[u]) continue;
            parent[v] = u;
            sum[v] = sum[u] + w;
            dist[v] = dist[u] + 1;
            st.push(v);
        }
    }

    sack(0, -1);

    if (ret == LLONG_MAX) {
        return -1;
    }
    return (int)ret;
}

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