Submission #1011572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011572		VMaksimoski008	봉쇄 시간 (IOI23_closing)	C++17	8 / 100	96 ms	35520 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
 
int n, x, y;
long long k;
vector<vector<pair<int, int> >> graph;
const int maxn = 2e5 + 5;
using ll = long long;
ll dist[2][maxn];
 
void dfs(int u, int p, int t) {
    for(auto &[v, w] : graph[u]) {
        if(v == p) continue;
        dist[t][v] = dist[t][u] + w;
        dfs(v, u, t);
    }
}
 
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    x = X;
    y = Y;
    k = K;
    graph.resize(n);
    if(x > y) swap(x, y);
 
    bool line = 1;
    for(int i=0; i<n-1; i++) {
        if(abs(U[i] - V[i]) != 1) line = 0;
        graph[U[i]].push_back({ V[i], W[i] });
        graph[V[i]].push_back({ U[i], W[i] });
    }
 
    if(line && n <= 500) {
        int ans = 0;
        dfs(x, x, 0);
        dfs(y, y, 1);
 
        ll pref[n][2];
        memset(pref, 0, sizeof(pref));
        pref[0][0] = min(dist[0][0], dist[1][0]);
        pref[0][1] = max(dist[0][0], dist[1][0]);
        priority_queue<ll> pq;
        pq.push(-pref[0][0]);
        for(int i=1; i<n; i++) {
            pref[i][0] = pref[i-1][0] + min(dist[1][i], dist[0][i]);
            pref[i][1] = pref[i-1][1] + max(dist[1][i], dist[0][i]);
            pq.push(-min(dist[0][i], dist[1][i]));
        }

        int res = 0;
        ll sum = 0;
        while(!pq.empty()) {
            int u = -pq.top(); pq.pop();
            // cout << u << '\n';
            if(sum + u > k) break;
            sum += u;
            res++;
        }

        auto query = [&](int l, int r, int t) {
            return pref[r][t] - (l ? pref[l-1][t] : 0);
        };

        for(int i=0; i<=x; i++) {
            for(int j=y; j<n; j++) {
                if(query(i, j, 0) > k) break;
                int ans2 = j - i + 1;

                // for(int x=p; p<=j; p++) {
                //     int l=p, r=j, pos=p-1;
                //     while(l <= r) {
                //         int mid = (l + r) / 2;
                //         if(query(p, mid, 1) + query(i, j, 0) <= k) pos = mid, l = mid + 1;
                //         else r = mid - 1;
                //     }
                //     ans = max(ans, j - i + 1 + pos - p + 1);
                // }

                ans = max(ans, ans2);
            }
        }
 
        return max(ans, res);
    }
 
    int ans = 0;
    ll total = k;
    dfs(x, x, 0);
    dfs(y, y, 1);
    
    vector<ll> v;
    for(int i=0; i<2; i++)
        for(int j=0; j<n; j++) v.push_back(dist[i][j]);
    sort(v.begin(), v.end());
 
    for(auto &x : v) {
        if(x > total) break;
        ans++;
        total -= x;
    }
 
    for(int i=0; i<n; i++) {
        graph[i].clear();
        for(int j=0; j<2; j++) dist[j][i] = 0;
    }
 
    return ans;
}

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