Submission #893472

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

ll k1, k2, ans, ans1, ans2;
vector<vector<pair<ll, ll>>> adj;
vector<ll> distX, distY;
vector<pair<ll, ll>> cost;

pqueue<pair<ll, ll>> pqa, pq1, pq2, pq3;

void dfs_x (ll i, ll cnt, ll from) {
    distX[i] = cnt;
    for (auto k : adj[i]) {
        if (k.first != from) {
            dfs_x(k.first, cnt + k.second, i);
        }
    }
}

void dfs_y (ll i, ll cnt, ll from) {
    distY[i] = cnt;
    for (auto k : adj[i]) {
        if (k.first != from) {
            dfs_y(k.first, cnt + k.second, i);
        }
    }
    cost[i].first = min(distX[i], distY[i]);
    cost[i].second = max(distX[i], distY[i]) - cost[i].first;
}

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);
    
    distX.clear();
    distX.resize(N);

    distY.clear();
    distY.resize(N);

    cost.clear();
    cost.resize(N);

    while (!pqa.empty()) pqa.pop();
    while (!pq1.empty()) pq1.pop();
    while (!pq2.empty()) pq2.pop();
    while (!pq3.empty()) pq3.pop();

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

    k1 = k2 = K;
    ans = ans1 = ans2 = 0;

    dfs_x(X, 0, X);
    dfs_y(Y, 0, Y);
    
    vector<ll> memo (N);
    range (i, 0, N) {
        pqa.push({-cost[i].first, i});
        
        // TYPE 2: BELONGS TO THE PATH X => Y
        if (2 * cost[i].first + cost[i].second == distX[Y]) {
            k2 -= cost[i].first;
            ans2++;
            pq1.push({-cost[i].second, i});
            memo[i]++;
            // cout << "[ " << i << " ] ";
        }
        // TYPE 1: lv1 >= lv2
        else if (cost[i].first >= cost[i].second) {
            pq3.push({-cost[i].first, i});
            pq2.push({-(cost[i].first + cost[i].second), i});
        }
        // TYPE 0: DEFAULT
        else {
            pq1.push({-cost[i].first, i});
            pq1.push({-cost[i].second, i});
        }
    }

    while (!pqa.empty() && k1 + pqa.top().first >= 0) {
        k1 += pqa.top().first;
        pqa.pop();
        ans1++;
    }
    ans = ans1;

    pair<ll, ll> t;
    if (k2 >= 0) {
        while (!pq2.empty() && k2 + pq2.top().first >= 0) {
            if (pq1.size() < 2) {
                k2 += pq2.top().first;
                if (k2 >= 0) {
                    memo[pq2.top().second] = 2;
                    ans2 += 2;
                    // cout << "[ " << pq2.top().second << ", lv2 ] ";
                    pq2.pop();
                    continue;
                }
            }

            t = pq1.top(); pq1.pop();
            if (pq1.top().first + t.first > pq2.top().first && k2 + t.first >= 0) {
                k2 += t.first;
                ans2++;
                // cout << "[ " << t.second << " ] ";
                memo[t.second]++;
            }
            else if (pq2.top().first + k2 >= 0) {
                k2 += pq2.top().first;
                pq1.push(t);
                ans2 += 2;
                // cout << "[ " << pq2.top().second << ", lv2 ] ";
                memo[pq2.top().second] = 2;
                pq2.pop();
            }
        }

        while (!pq1.empty() && k2 + pq1.top().first >= 0) {
            k2 += pq1.top().first; 
            ans2++;
            memo[pq1.top().second]++;
            // cout << "[ " << pq1.top().second << " ] ";
            pq1.pop();
        }

        while (!pq3.empty() && memo[pq3.top().second] != 0) pq3.pop();
        if (!pq3.empty() && pq3.top().first + k2 >= 0) ans2++;

        ans = max(ans, ans2);
    }

    cout << '\n';
    return ans;
} 

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