Submission #891341

#	Time	Username	Problem	Language	Result	Execution time	Memory
891341		Maaxle	Closing Time (IOI23_closing)	C++17	17 / 100	98 ms	26596 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
    
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 ((ll) 1 << 30)
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue
    
using namespace std;
    
vector<vector<pair<ll, ll>>> adj;
vector<ll> memo;

struct TPos {
    ll i, wth = -INF64, from;

    string toString() {
        return to_string(i) + ":" + to_string(wth) + ":" + to_string(from);
    }
};
bool operator < (const TPos& a, const TPos& b) {
    return (a.wth - memo[a.i] > b.wth - memo[b.i]);
}
bool operator == (const TPos& a, const TPos& b) {
    return (a.i == b.i && a.from == b.from && a.wth == b.wth);
}

vector<TPos> fut;

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    adj.clear();
    adj.resize(N);
    
    memo.clear();
    memo.resize(N);

    fut.clear();
    fut.resize(N);

    range(i, 0, N - 1){
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    
    pqueue<TPos> pq;
    pq.push({X, 0, X});
    fut[X] = {X, 0, X};
    pq.push({Y, 0, Y});
    fut[Y] = {Y, 0, Y};

    ll ans = 0;
    ll sum = 0;
    TPos t;
    while (!pq.empty()) {
        t = pq.top(); pq.pop();
        if (fut[t.i].wth == -INF64) continue;
        if (t == fut[t.i]) fut[t.i].wth = -INF64;

        ll dif = t.wth - memo[t.i];
        if (sum + dif > K) break;

        // cout << t.toString() << "  |  ";

        memo[t.i] = t.wth;
        if (fut[t.i].wth != -INF64)
            pq.push(fut[t.i]);

        for (pair<ll, ll> a : adj[t.i]) {
            if (a.first != t.from) {
                pq.push({a.first, t.wth + a.second, t.i});
                if (t.wth + a.second >= fut[a.first].wth) {
                    fut[a.first] = {a.first, t.wth + a.second, t.i};
                }
            }
        }

        // range(i, 0, N) cout << "[ " << fut[i].toString() << " ] ";
        // cout << '\n';

        ans++;
        sum += dif;
    }

    // cout << "----------------\n";
    
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 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