Submission #1248831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248831		madamadam3	Closing Time (IOI23_closing)	C++20	0 / 100	1093 ms	20948 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 <= x; i1++) {
        for (int i2 = x; i2 < n; i2++) {
            for (int j1 = 0; j1 <= y; j1++) {
                for (int j2 = y; j2 < n; j2++) {
                    int amt = (i2 - i1 + 1) + (j2 - j1 + 1);
                    int jj = max(j1, i2 + 1);
                    ll c = (prefix[i2+1] - prefix[i1]) + (prefix[j2+1] - prefix[jj]);

                    if (c <= k) best = max(best, amt);
                }
            }
        }
    }

    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