Submission #1212667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212667		trimkus	Closing Time (IOI23_closing)	C++20	35 / 100	52 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 itleft = 0; itleft < N; ++itleft) {
        ll sum = 0;
        ll curr = 0;
        vector<ll> C(N), ps(N);
        int now = itleft + 1;
        int id = idx[X];
        bool ok = true;
        for (int it = 0; it <= itleft; ++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;
        }
        int left = 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;
        auto upd = [&]() -> void {
            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;
                    leftsum += W[1][leftid - 1];
                    C[leftid - 1] = max(leftsum, C[leftid - 1]);
                    leftid -= 1;
                } else {
                    sum += take_right;
                    rightsum += W[1][rightid + 1];
                    C[rightid + 1] = max(rightsum, C[rightid + 1]);
                    rightid += 1;
                }
            }
        };
        upd();
        res = max(res, itleft + 1 + rightid - leftid + 1);
        // 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]);
            sum += add;
            while (sum > K) {
                ll take_left = 0, take_right = 0;
                if (leftid + 1 <= idx[Y]) {
                    take_left = max(0LL, leftsum - ps[leftid]);
                }
                if (rightid - 1 >= idx[Y]) {
                    take_right = max(0LL, rightsum - ps[rightid]);
                }
                if (max(take_left, take_right) == 0) break;
                // cout << take_left << " = " << leftsum << " " << ps[leftid] << "\n";
                // cout << take_right << " = " << rightsum << " " << ps[rightid] << "\n";
                if (take_left > take_right) {
                    sum -= take_left;
                    C[leftid] = ps[leftid];
                    leftsum -= W[1][leftid];
                    leftid += 1;
                } else {
                    sum -= take_right;
                    C[rightid] = ps[rightid];
                    rightsum -= W[1][rightid];
                    rightid -= 1;
                }
                now -= 1;
            }
            if (sum > K) continue;
            upd();
            C[right] += add;
            ps[right] = curr;
            // cout << left << " " << right << ":\n";
            // for (int i = 0; i < N; ++i) {
            //     cout << ps[i] << " ";
            // }
            // cout << "\n";
            // for (int i = 0; i < N; ++i) {
            //     cout << C[i] << " ";
            // }
            // cout << "\n\n";
            
            now += 1;
            // cerr << left << " " << right << " " << leftid << " " << rightid << " = " << now << "\n";
            res = max(res, right - left + 1 + rightid - leftid + 1);
        }
    }
    return res;
}

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