제출 #1245733

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245733		inkvizytor	Race (IOI11_race)	C++20	100 / 100	201 ms	104948 KiB

race

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

#define ll long long

class MAP {
    unordered_map<ll, ll> mp;
    ll a = 0, b = 0;
    public:
    ll get(ll key) {
        if (!mp.contains(key-a)) {
            return -1;
        }
        return mp[key-a]+b;
    }
    void increase(ll x) {
        a += x;
        b++;
    }
    void insert(ll key, ll val) {
        key -= a;
        val -= b;
        if (!mp.contains(key)) {
            mp[key] = val;
        }
        else {
            mp[key] = min(mp[key], val);
        }
    }
    vector<pair<ll, ll>> clear() {
        vector<pair<ll, ll>> v;
        for (auto i : mp) {
            v.push_back({i.first+a, i.second+b});
        }
        mp = unordered_map<ll, ll>();
        a = 0;
        b = 0;
        return v;
    }
    int size() {
        return (int)mp.size();
    }
};

void dfs (int v, vector<vector<pair<ll, ll>>> &g, vector<bool> &odw, vector<MAP> &mp, vector<int> &wsk, ll &w, int k) {
    //cout << v << '\n';
    odw[v] = 1;
    vector<pair<int, int>> x;
    for (auto u : g[v]) {
        if (!odw[u.first]) {
            dfs(u.first, g ,odw, mp, wsk, w, k);
            mp[wsk[u.first]].increase(u.second);
            x.push_back({mp[wsk[u.first]].size(), wsk[u.first]});
            //cout << "wsk " <<  u.first << ' ' << wsk[u.first] << '\n';
        }
    }
    if (x.empty()) {
        wsk[v] = mp.size();
        mp.push_back(MAP());
        mp[wsk[v]].insert(0, 0);
        return;
    }
    sort(x.begin(), x.end(), greater<pair<int, int>>());
    wsk[v] = x[0].second;
    mp[wsk[v]].insert(0, 0);
    ll q = mp[wsk[v]].get(k);
    if (q != -1) {
        //cout << v << ' ' << q << '\n';
        w = min(w, q);
    }
    for (int i = 1; i < (int)x.size(); i++) {
        vector<pair<ll, ll>> p = mp[x[i].second].clear();
        //cout << "i " << x[i].second << '\n';
        for (auto j : p) {
            //cout << j.first << ' ' << j.second << '\n';
            ll a = mp[wsk[v]].get(k-j.first);
            if (a != -1) {
                w = min(w, a+j.second);
            }
        }
        for (auto j : p) {
            mp[wsk[v]].insert(j.first, j.second);
        }
    }
}

int best_path(int n, int k, int H[][2], int L[])
{
    vector<vector<pair<ll, ll>>> g (n);
    for (int i = 0; i < n-1; i++) {
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    vector<bool> odw (n, 0);
    vector<MAP> mp;
    vector<int> wsk (n, 0);
    ll w = 1e9; 
    dfs(0, g, odw, mp, wsk, w, k);
    if (w == (ll)1e9) {
        return -1;
    }
    return (int)w;
}

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