Submission #1068555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068555		Arapak	Closing Time (IOI23_closing)	C++17	8 / 100	123 ms	28488 KiB

closing

// Author: Kajetan Ramsza
#include "closing.h"
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;

#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto, auto> &p) {
    return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
    os<<"{";
    for(auto it=begin(v);it!=end(v);++it) {
        if(it!=begin(v)) os<<", ";
        os<<(*it);
    }
    return os<<"}";
}

void dbg_out(auto... x) {
    ((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

const ll inf = ll(1e18) + 7;

int n, x, y;
ll K;
vector<vector<pair<int, ll>>> g;
vll dist_x, dist_y;

int solve() {
    using T = tuple<ll, int, int>;
    priority_queue<T, vector<T>, greater<T>> q;
    vector<ll> closing(n, 0);
    
    ll k = K;
    int res = 2;

    auto visited = [&](int v, int root) -> bool {
        return closing[v] >= (root == x ? dist_x[v] : dist_y[v]);
    };
    auto add_new = [&](int v, int root) {
        if(!visited(v, root)) return;
        dbg(v, root);
        for(auto [e, d] : g[v]) {
            if(visited(e, root)) continue;
            q.push({(root == x ? dist_x[e] : dist_y[e]) - closing[e], e, root});
        }
    };

    add_new(x, x);
    add_new(y, y);

    while(!q.empty()) {
        auto [cost, v, root] = q.top(); q.pop();
        if(visited(v, root)) continue;
        dbg(cost, v, root);
        if(cost > k) return res;
        k -= cost;
        closing[v] = root == x ? dist_x[v] : dist_y[v];
        res++;
        add_new(v, root);
    }
    return res;
}

vll distance(int root) {
    queue<int> q;
    q.push(root);
    vll dist(n, inf);
    dist[root] = 0;
    while(!q.empty()) {
        int v = q.front(); q.pop();
        for(auto [e, d] : g[v]) {
            if(dist[e] < inf) continue;
            dist[e] = dist[v] + d;
            q.push(e);
        }
    }
    return dist;
}

int max_score(int N, int X, int Y, ll _K,
             vi U, vi V, vi W) {
    n = N; x = X; y = Y; K = _K;
    dbg(n, x, y, K);
    g.resize(n);
    rep(i,0,n-1) {
        g[U[i]].emplace_back(V[i], W[i]);
        g[V[i]].emplace_back(U[i], W[i]);
    }
    dist_x = distance(x);
    dist_y = distance(y);
    int result = solve();
    g.clear();
    dist_x.clear();
    dist_y.clear();
    return result;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17