Submission #136944

#	Time	Username	Problem	Language	Result	Execution time	Memory
136944		mlyean00	Race (IOI11_race)	C++17	9 / 100	119 ms	10292 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200'000;

int n, k;
int ans = INT_MAX;

struct state {
    int delta_k = 0;
    int delta_v = 0;
    map<int, int> min_n;

    state() {
        min_n[0] = 0;
    }

    void incr(int d) {
        delta_k += d;
        ++delta_v;
        auto it = min_n.find(k - delta_k);
        if (it != min_n.end()) ans = min(ans, it->second + delta_v);
        min_n.erase(min_n.upper_bound(k - delta_k), min_n.end());
    }

    void merge(state other) {
        if (min_n.size() < other.min_n.size()) {
            swap(delta_k, other.delta_k);
            swap(delta_v, other.delta_v);
            swap(min_n, other.min_n);
        }

        for (pair<int, int> const& p : other.min_n) {
            int key, val;
            tie(key, val) = p;
            key += other.delta_k;
            val += other.delta_v;
            auto it = min_n.find(key - delta_k);
            if (it == min_n.end()) {
                it = min_n.insert({key - delta_k, val - delta_v}).first;
            } else if (val < it->second + delta_v) {
                it->second = val - delta_v;
            }
            int rem = k - key;
            auto it2 = min_n.find(rem - delta_k);
            if (it2 != min_n.end()) {
                ans = min(ans, val + it2->second + delta_v);
            }
        }
    }
};

vector<int> g[MAX_N];
int parent[MAX_N];
int len[MAX_N];

void dfs1(int u) {
    for (int v : g[u]) {
        if (v == parent[u]) continue;
        parent[v] = u;
        dfs1(v);
    }
}

state dfs2(int u) {
    state st;
    for (int v : g[u]) {
        if (parent[v] == u) st.merge(dfs2(v));
    }
    st.incr(len[u]);
    return st;
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;
    for (int i = 0; i < n - 1; ++i) {
        g[H[i][0]].push_back(H[i][1]);
        g[H[i][1]].push_back(H[i][0]);
    }

    dfs1(0);
    for (int i = 0; i < n - 1; ++i) {
        if (parent[H[i][1]] == H[i][0]) swap(H[i][0], H[i][1]);
        len[H[i][0]] = L[i];
    }
    dfs2(0);

    return ans == INT_MAX ? -1 : ans;
}

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