Submission #1178713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178713		madamadam3	Closing Time (IOI23_closing)	C++20	9 / 100	1097 ms	49776 KiB

closing

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

using namespace std;

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using pi = pair<int, int>;
using pli = pair<ll, int>;
using vb = vector<bool>;

int N, X, Y; ll K;
vi U, V; vl W;
vvi adj; map<pi, int> weights;

vl compute_distances(int start) {
    vl distances(N, 0LL);
    vi parent(N, -1);

    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) { 
            if (v == parent[u]) continue;
            
            q.push(v);
            distances[v] = distances[u] + weights[{u, v}];
            parent[v] = u;
        }
    }

    return distances;
}

void bfs_cap(int maxnodes, vl &tim, vb &vis, vl &xdist, int &seen, ll &cur_sum) {
    priority_queue<pli, vector<pli>, greater<pli>> q;
    q.push({0LL, X});

    while (!q.empty()) {
        int u = q.top().second;
        ll dist = q.top().first;
        q.pop();

        if (vis[u]) continue;
        if (seen >= maxnodes) break;
        vis[u] = true;
        seen++;

        cur_sum += dist;
        tim[u] = dist;

        for (int v : adj[u]) {
            if (vis[v]) continue;
            q.push({xdist[v], v});
        }
    }
}

void bfs_rem(vl &tim, vb &vis, vl &xdist, vl &ydist, int &seen, ll &cur_sum) {
    vb newvis(N, false);
    priority_queue<pli, vector<pli>, greater<pli>> q;
    q.push({0LL, Y});

    while (!q.empty()) {
        int u = q.top().second;
        ll dist = q.top().first;
        q.pop();

        if (newvis[u]) continue;
        if (cur_sum + dist > K) break;
        newvis[u] = true;

        seen++;
        cur_sum += dist;
        tim[u] = dist;

        for (int v : adj[u]) {
            if (newvis[v]) continue;
            ll ndist = ydist[v];
            if (vis[v]) ndist = max(0LL, ydist[v] - xdist[v]);
            q.push({ndist, v});
        }
    }
}

int get_reachable(int x_cap, vl &xdist, vl &ydist) {
    vl tim(N, 0LL);
    vb vis(N, false);
    int seen = 0;
    ll cur_sum = 0LL;

    bfs_cap(x_cap, tim, vis, xdist, seen, cur_sum);
    bfs_rem(tim, vis, xdist, ydist, seen, cur_sum);

    if (cur_sum > K) return 0;
    return seen;
}

int solve() {
    vl distX = compute_distances(X), distY = compute_distances(Y);

    
    int mx = 0;
    for (int i = 1; i <= N; i++) {
        int v = get_reachable(i, distX, distY);
        mx = max(mx, v);
    }

    return mx;
}

/*
    N: number of cities <= 200k
    X, Y: 2 cities of interest 0 < X != Y < N
    K: maximum allowed sum of closing times <= 10^18
    U, V: road[j] = (U[j], V[j])
    W: W[j] = length of road[W]
*/
int max_score(int _N, int _X, int _Y, ll _K, vi _U, vi _V, vi _W) {
    W.resize(0); weights.clear();
    N = _N; X = _X; Y = _Y; K = _K; U = _U; V = _V; for (int i = 0; i < N - 1; i++) W.push_back(ll(_W[i]));
    adj.assign(N, vi());

    bool line = true;
    for (int i = 0; i < N - 1; i++) {
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
        weights[{U[i], V[i]}] = W[i];
        weights[{V[i], U[i]}] = W[i];

        line = line && max(U[i], V[i]) == min(U[i], V[i]) + 1;
    }

    int ans = solve();
    return ans;
}

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