Submission #891367

#	Time	Username	Problem	Language	Result	Execution time	Memory
891367		Maaxle	Closing Time (IOI23_closing)	C++17	17 / 100	75 ms	34388 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;
    bool from_x;

    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]);
}

struct Fut {
    TPos px, py;
};

vector<Fut> 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, 1});
    fut[X].px = {X, 0, X, 1};
    pq.push({Y, 0, Y, 0});
    fut[Y].py = {Y, 0, Y, 0};

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

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

        ans++;
        sum += dif;
        memo[t.i] = t.wth;

        if (t.from_x) {
            fut[t.i].px.wth = -INF64;
            if (fut[t.i].py.wth != -INF64)
                pq.push({fut[t.i].py});
        } 
        else {
            fut[t.i].py.wth = -INF64;
            if (fut[t.i].px.wth != -INF64)
                pq.push({fut[t.i].px});
        } 

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

                if (t.from_x) fut[nt.i].px = nt;
                else fut[nt.i].py = nt;
            }
        }
    }
    
    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