Submission #1212640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212640		trimkus	봉쇄 시간 (IOI23_closing)	C++20	9 / 100	53 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), ps(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;
            }
            curr += W[0][id];
            if (sum + curr - C[id] > K) {
                ok = false;
                break;
            }
            sum += curr - C[id];
            C[id] = curr;
            ps[id] = curr;
            id -= 1;
        }
        if (!ok) continue;
        curr = 0;
        id = idx[X];
        vector<array<ll, 3>> rollback;
        int leftid = idx[Y], rightid = idx[Y];  
        ll leftsum = 0, rightsum = 0;
        now += 1;
        while (true) {
            ll take_left = K, take_right = K;
            if (leftid - 1 >= 0) {
                take_left = max(0LL, leftsum + W[1][leftid - 1] - C[leftid - 1]);
            }
            if (rightid + 1 < N) {
                take_right = max(0LL, rightsum + W[1][rightid + 1] - C[rightid + 1]);
            }
            if (sum + min(take_left, take_right) > K) {
                break;
            }
            if (take_left < take_right) {
                sum += take_left;
                rollback.push_back({0, C[leftid - 1], take_left});
                leftsum += W[1][leftid - 1];
                C[leftid - 1] = max(leftsum, C[leftid - 1]);
                leftid -= 1;
            } else {
                sum += take_right;
                rollback.push_back({1, C[rightid + 1], take_right});
                rightsum += W[1][rightid + 1];
                C[rightid + 1] = max(rightsum, C[rightid + 1]);
                rightid += 1;
            }
            now += 1;
        }
        res = max(res, now);
        // cerr << left << " = " << leftid << " " << rightid << "\n";
        curr = 0;
        for (int right = idx[X] + 1; right < N; ++right) {
            curr += W[0][right];
            ll add = max(0LL, curr - C[right]);
            while (rollback.size() > 0 && sum + add > K) {
                int p = rollback.back()[0];
                ll pC = rollback.back()[1];
                ll w = rollback.back()[2];
                rollback.pop_back();
                if (p == 0) {
                    C[leftid] = pC;
                    sum -= w;
                    if (ps[leftid] > C[leftid]) {
                        sum += ps[leftid] - C[leftid];
                        C[leftid] = ps[leftid];
                    }
                    leftid++;
                } else {
                    sum -= w;
                    C[rightid] = pC;
                    if (ps[rightid] > C[rightid]) {
                        sum += ps[rightid] - C[rightid];
                        C[rightid] = ps[rightid];
                    }
                    rightid--;
                }
                now -= 1;
            }
            sum += add;
            if (sum > K) continue;
            C[right] += add;
            ps[right] = curr;
            now += 1;
            res = max(res, now);
        }
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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