Submission #1248872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248872		madamadam3	봉쇄 시간 (IOI23_closing)	C++20	0 / 100	1096 ms	21060 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;

struct Edge {
    int v, w;
};

int n, x, y;
ll k;
vi xi, yi, wi;
vector<vector<Edge>> adj;
const ll INF = 4e18;

int disconnected() {
    int ans = 0;
    ll tl = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    q.push({0, x}), q.push({0, y});
    vector<bool> vis(n, false);

    while (tl <= k && !q.empty()) {
        auto cur = q.top(); q.pop();
        vis[cur.second] = true;

        if (tl + cur.first > k) break;
        tl += cur.first;
        ans++;

        for (auto &e : adj[cur.second]) {
            if (vis[e.v]) continue;
            q.push({cur.first + ll(e.w), e.v});
        }
    }
    
    return ans;
}

int linear() {
    int best = 0;
    vector<ll> prefix(n+1, 0);
    for (int i = 1; i < n; i++) prefix[i+1] += prefix[i] + wi[i - 1];

    for (int i1 = 0; i1 < n; i1++) {
        for (int j1 = i1; j1 < n; j1++) {
            if (!(i1 <= x && x <= j1)) continue;
            for (int i2 = 0; i2 < n; i2++) {
                for (int j2 = i2; j2 < n; j2++) {
                    if (!(i2 <= y && y <= j2)) continue;
                    int L = max(i1, i2), R = min(j1, j2);
                    ll inter = L <= R ? (prefix[R+1] - prefix[L]) : 0LL;
                    ll s1 = (prefix[j1+1] - prefix[i1]), s2 = (prefix[j2+1] - prefix[i2]);
                    
                    if (s1 + s2 + inter <= k) {
                        best = max(best, (j1 - i1 + 1) + (j2 - i2 + 1));
                    }
                }
            }
        }
    }

    return best;
}

int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) {
    n = N; x = X; y = Y; k = K; xi = U; yi = V; wi = W;
    adj.assign(n, vector<Edge>());
    for (int i = 0; i < n - 1; i++) {
        adj[xi[i]].push_back(Edge{yi[i], wi[i]});
        adj[yi[i]].push_back(Edge{xi[i], wi[i]});
    }

    // return disconnected();
    return linear();
}

• 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