제출 #1212613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1212613		trimkus	봉쇄 시간 (IOI23_closing)	C++20	0 / 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";
    auto calc = [&](int id, int right, ll sum, ll curr, vector<ll> C) -> int {
        int now = 0;
        bool ok = true;
        for (;id <= right;) {
            if (id >= N) {
                assert(false);
                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;
            now += 1;
        }
        if (!ok) {
            return -N;
        }
        // cerr << left << " " << right << " = ";
        // for (int i = 0; i < N; ++i) {
        //     cerr << C[i] << " ";
        // }
        // cerr << "\n";
        ll left_sum = 0, right_sum = 0;
        id = idx[Y];
        int leftid = id, rightid = id;
        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;
                sum += pick_left;
                left_sum += W[1][leftid];
                C[line[leftid]] += pick_left;
            } else {
                rightid += 1;
                now += 1;
                sum += pick_right;
                right_sum += W[1][rightid];
                C[line[rightid]] += pick_right;
            }
        }
        // cout << left << " " << right << " = " << now << "\n";
        // cout << "C = ";
        // for (auto& u : C) {
        //     cout << u << " ";
        // }
        // cout << "\n";
        return now;
    };
    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) break;
        int l = idx[X], r = N - 2;
        curr = 0;
        id = idx[X];
        while (l < r) {
            int m = (l + r) / 2;
            ll left = calc(id, m, sum, curr, C);
            ll right = calc(id, m + 1, sum, curr, C);
            if (left < 0) {
                r = m - 1;
                continue;
            }
            if (left >= right) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        now += calc(id, r, sum, curr, C);
        cerr << left << " = " << now << "\n";
        res = max(res, now);
    }
    return res;
}

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