Submission #885886

#	Time	Username	Problem	Language	Result	Execution time	Memory
885886		bobbilyking	Race (IOI11_race)	C++17	43 / 100	231 ms	101304 KiB

race

#include "race.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
#define NN 200010
#define F(i, l, r) for (ll i = (l); i < (r); ++i)
vector<pl> adj[NN];
struct mp {
    ll plen = 0, pwe = 0;
    map<ll, ll> mp; // maps weight -> lens, lazy updates and shit

    void insert(ll k, ll w) {
        k -= pwe; w -= plen;
        if (!mp.count(k)) mp[k] = w;
        else mp[k] = min(w, mp[k]);
    }

    ll query(ll k) {
        k -= pwe;
        if (!mp.count(k)) return 1e9;
        return mp[k] + plen;
    }

    vector<pl> getall() const {
        vector<pl> res;
        for (const auto &[k, v]: mp) res.emplace_back(k + pwe, v + plen);
        return res;
    }
};
ll ans, k;

mp dfs(ll i, ll p) {
    mp cur;
    for (auto [x, w]: adj[i]) if (x-p) {
        auto child = dfs(x, i);
        child.plen++; child.pwe+=w;
        ans = min(ans, cur.query(k)); 
        if (cur.mp.size() < child.mp.size()) swap(cur, child);
        for (const auto [cpath, clen]: child.getall()) {
            ans = min(ans, cur.query(k - cpath) + clen);
            cur.insert(cpath, clen);
        }
    }

    ans = min(ans, cur.query(k));
    cur.insert(0, 0);
    return cur;
}

int best_path(int N, int K, int H[][2], int L[])
{
    F(i, 0, N-1) {
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }

    ans = N;
    k = K;

    dfs(0, 0);

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

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