Submission #847282

#	Time	Username	Problem	Language	Result	Execution time	Memory
847282		sebinkim	Closing Time (IOI23_closing)	C++17	100 / 100	215 ms	58272 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

vector<pll> T[202020];
ll X[202020], Y[202020];
int n; ll l;

void dfs(int u, int p, ll *X) {
    for (auto &[v, w]: T[u]) if (v != p) {
        X[v] = X[u] + w;
        dfs(v, u, X);
    }
}

int solve1(ll k) {
    vector<ll> V;
    int i;
    for (i = 0; i < n; i++) {
        V.push_back(X[i]);
        V.push_back(Y[i]);
    }
    sort(V.begin(), V.end());
    for (i = 0; i < n + n; i++) {
        k -= V[i];
        if (k < 0) break;
    }
    return i;
}

ll D[6060];
int solve2(ll k) {
    priority_queue<pll> P01, P02, P10, P12, P21;
    vector<ll> C(n, 0);
    int i;

    for (i = 0; i < n; i++) {
        if (X[i] > Y[i]) swap(X[i], Y[i]);
        if (X[i] + Y[i] == l) {
            k -= X[i]; Y[i] -= X[i]; X[i] = 0;
        }
        Y[i] -= X[i];

        P01.emplace(-X[i], i);
        P02.emplace(-X[i] - Y[i], i);
    }
    if (k < 0) return 0;

    for (i = 0; i < n + n; i++) {
        ll m = -1e18; int f;

        for (; !P01.empty() && C[P01.top().second] != 0; P01.pop());
        for (; !P02.empty() && C[P02.top().second] != 0; P02.pop());
        for (; !P10.empty() && C[P10.top().second] != 1; P10.pop());
        for (; !P12.empty() && C[P12.top().second] != 1; P12.pop());
        for (; !P21.empty() && C[P21.top().second] != 2; P21.pop());

        if (!P01.empty()) {
            auto [t, _] = P01.top();
            if (m < t) m = t, f = 1;
        }
        if (!P12.empty()) {
            auto [t, _] = P12.top();
            if (m < t) m = t, f = 2;
        }
        if (!P10.empty() && !P02.empty()) {
            auto [t1, _] = P10.top();
            auto [t2, __] = P02.top();
            ll t = t1 + t2;
            if (m < t) m = t, f = 3;
        }
        if (!P21.empty() && !P02.empty()) {
            auto [t1, _] = P21.top();
            auto [t2, __] = P02.top();
            ll t = t1 + t2;
            if (m < t) m = t, f = 4;
        }

        k += m;
        if (k < 0) break;

        if (f == 1) {
            auto [t, j] = P01.top(); P01.pop();
            P10.emplace(X[j], j);
            P12.emplace(-Y[j], j);
            C[j] = 1;
        } else if (f == 2) {
            auto [t, j] = P12.top(); P12.pop();
            P21.emplace(Y[j], j);
            C[j] = 2;
        } else if (f == 3) {
            auto [t1, j1] = P10.top(); P10.pop();
            P01.emplace(-X[j1], j1);
            P02.emplace(-X[j1] - Y[j1], j1);
            C[j1] = 0;

            auto [t2, j2] = P02.top(); P02.pop();
            C[j2] = 2;
        } else if (f == 4) {
            auto [t1, j1] = P21.top(); P21.pop();
            P10.emplace(X[j1], j1);
            P12.emplace(-Y[j1], j1);
            C[j1] = 1;

            auto [t2, j2] = P02.top(); P02.pop();
            P21.emplace(Y[j2], j2);
            C[j2] = 2;
        }
    }

    return i;
}

int max_score(int n, int x, int y, ll k, vector<int> U, vector<int> V, vector<int> W) {
    ::n = n;
    int i;
    for (i = 0; i < n; i++) {
        T[i].clear();
    }
    for (i = 0; i < n - 1; i++) {
        T[U[i]].emplace_back(V[i], W[i]);
        T[V[i]].emplace_back(U[i], W[i]);
    }
    X[x] = Y[y] = 0;
    dfs(x, x, X); dfs(y, y, Y);
    l = X[y];

    int a = solve1(k);
    a = max(a, solve2(k));

    return a;
}

Compilation message (stderr)

closing.cpp: In function 'int solve2(ll)':
closing.cpp:94:16: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |         } else if (f == 3) {
      |                ^~

• 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