Submission #1212627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212627		trimkus	Closing Time (IOI23_closing)	C++20	21 / 100	55 ms	20288 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> _W)
{
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < N - 1; ++i) {
        adj[U[i]].push_back({V[i], _W[i]});
        adj[V[i]].push_back({U[i], _W[i]});
    }
    vector<int> line;
    vector<int> idx(N);
    vector<vector<int>> W(2, vector<int>(N));
    {
        int p = -1;
        int v;
        for (int i = 0; i < N; ++i) {
            if ((int)adj[i].size() == 1) {
                v = i;
                break;
            }
        }
        line.push_back(v);
        while (true) {
            bool ok = false;
            for (auto& [u, w] : adj[line.back()]) {
                if (u == p) continue;
                p = line.back();
                line.push_back(u);
                ok = true;
                break;
            }
            if (!ok) break;
        }
        assert((int)line.size() == N);
        for (int i = 0; i < N; ++i) {
            idx[line[i]] = i;
        }
        int id = idx[X];
        while (id > 0) {
            int now = line[id];
            int to = line[id - 1];
            for (auto& [u, w] : adj[now]) {
                if (u == to) {
                    W[0][id - 1] = w;
                }
            }
            id--;
        }
        id = idx[X];
        while (id + 1 < N) {
            int now = line[id];
            int to = line[id + 1];
            for (auto& [u, w] : adj[now]) {
                if (u == to) {
                    W[0][id + 1] = w;
                }
            }
            id++;
        }
        id = idx[Y];
        while (id > 0) {
            int now = line[id];
            int to = line[id - 1];
            for (auto& [u, w] : adj[now]) {
                if (u == to) {
                    W[1][id - 1] = w;
                }
            }
            id--;
        }
        id = idx[Y];
        while (id + 1 < N) {
            int now = line[id];
            int to = line[id + 1];
            for (auto& [u, w] : adj[now]) {
                if (u == to) {
                    W[1][id + 1] = w;
                }
            }
            id++;
        }
    }
    
    int res = 0;
    // cout << "\nline = ";
    // for (int i  = 0; i < N; ++i) {
    //     cout << line[i] << " ";
    // }
    // cout << "\n";
    // cout << "X weights = ";
    // for (int i = 0; i < N; ++i) {
    //     cout << W[0][i] << " ";
    // }
    // cout << "\n";
    // cout << "Y weights = ";
    // for (int i = 0; i < N; ++i) {
    //     cout << W[1][i] << " ";
    // }
    // cout << "\n";
    cerr << idx[X] << " " << idx[Y] << "\n";
    for (int left = 0; left < N; ++left) {
        ll sum = 0;
        ll curr = 0;
        vector<ll> C(N);
        int now = left + 1;
        int id = idx[X];
        bool ok = true;
        for (int it = 0; it <= left; ++it) {
            if (id < 0) {
                ok = false;
                break;
            }
            int j = line[id];
            curr += W[0][id];
            if (sum + curr - C[j] > K) {
                ok = false;
                break;
            }
            sum += curr - C[j];
            C[j] = curr;
            id -= 1;
        }
        if (!ok) continue;

        ll left_sum = 0, right_sum = 0;
        id = idx[Y];
        now += 1;
        int leftid = id, rightid = id;
        vector<array<ll, 3>> op;
        while (true) {
            ll pick_left = K, pick_right = K;
            if (leftid - 1 >= 0) {
                int j = line[leftid - 1];
                pick_left = max(0LL, left_sum + W[1][leftid - 1] - C[j]);
            }
            if (rightid + 1 < N) {
                int j = line[rightid + 1];
                pick_right = max(0LL, right_sum + W[1][rightid + 1] - C[j]);
            }
            if (min(pick_left, pick_right) + sum > K) {
                break;
            }
            if (pick_left < pick_right) {
                leftid -= 1;
                now += 1;
                op.push_back({0, pick_left, C[line[leftid]]});
                sum += pick_left;
                left_sum += W[1][leftid];
                C[line[leftid]] += pick_left;
            } else {
                rightid += 1;
                now += 1;
                sum += pick_right;
                op.push_back({1, pick_right, C[line[rightid]]});
                right_sum += W[1][rightid];
                C[line[rightid]] += pick_right;
            }
        }
        curr = 0;
        for (int right = idx[X]; right < N; ++right) {
            id = right;
            int j = line[id];
            curr += W[0][id];
            while (sum + curr - C[j] > K && (int)op.size()) {
                auto [p, w, _C] = op.back();
                op.pop_back();
                if (p == 0) {
                    sum -= w;
                    C[line[leftid]] = _C;
                    leftid++;
                } else {
                    sum -= w;
                    C[line[rightid]] = _C;
                    rightid--;
                }
                now -= 1;
            }
            if (sum + max(0LL, curr - C[j]) > K) {
                break;
            }
            if (curr > C[j]) {
                sum += curr - C[j];
                C[j] = curr;
            }
            res = max(res, now);
            now += 1;
        }
    }
    return res;
}

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