Submission #890764

#	Time	Username	Problem	Language	Result	Execution time	Memory
890764		Maaxle	Closing Time (IOI23_closing)	C++17	8 / 100	180 ms	39620 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;

struct TPos {
    ll X, Y;
};

bool operator < (const TPos& a, const TPos& b) {
    return (max(a.X, a.Y) < max(b.X, b.Y));
}

vector<vector<pair<ll, ll>>> adj;
vector<ll> from_x, from_y;

void dfs_x (ll i, ll cnt) {
    from_x[i] = cnt;
    for (pair<ll, ll> k : adj[i]) {
        if (from_x[k.first] == INF64) {
            dfs_x(k.first, cnt + k.second);
        }
    }
}

void dfs_y (ll i, ll cnt) {
    from_y[i] = cnt;
    for (pair<ll, ll> k : adj[i]) {
        if (from_y[k.first] == INF64) {
            dfs_y(k.first, cnt + k.second);
        }
    }
}

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

    from_x.clear();
    from_x.resize(N, INF64);

    from_y.clear();
    from_y.resize(N, INF64);

    range(i, 0, N - 1){
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }

    ll ans = 2*N;
    dfs_x(X, 0);
    dfs_y(Y, 0);

    pqueue<TPos> pq;
    ll sum = 0;
    range(i, 0, N) {
        pq.push({from_x[i], from_y[i]});
        sum += max(from_x[i], from_y[i]);
    }

    while (sum > K) {
        TPos t = pq.top(); pq.pop();
        
        if (t.X > t.Y) {
            ll dif = t.X - t.Y;
            t.X = 0;
            ans--;
            sum -= dif;
        }
        else {
            ll dif = t.Y - t.X;
            t.Y = 0;
            ans--;
            sum -= dif;
        }

        pq.push(t);
    }

    return ans;
}

• 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