Submission #940509

#	Time	Username	Problem	Language	Result	Execution time	Memory
940509		Ghetto	Closing Time (IOI23_closing)	C++17	9 / 100	1068 ms	31596 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pil = pair<int, lint>;
using pli = pair<lint, int>;
const int MAX_N = 2e5 + 5;
const lint INF = 5e18;

int n, x, y;
lint k;
vector<pil> adj[MAX_N];

bool seen[MAX_N];
lint min_dist[MAX_N];
priority_queue<pli, vector<pli>, greater<pli>> order;
void dijk(int s) {
    for (int i = 0; i <= n - 1; i++) {
        min_dist[i] = INF;
        seen[i] = false;
    } 

    min_dist[s] = 0;
    order.push({0, s});

    while (order.size()) {
        int u = order.top().second;
        order.pop();

        if (seen[u]) continue;
        seen[u] = true;

        for (pil e : adj[u]) {
            lint new_dist = min_dist[u] + e.second;
            
            if (new_dist >= min_dist[e.first]) continue;
            min_dist[e.first] = new_dist;
            order.push({new_dist, e.first});
        }
    }
}

lint x_dist[MAX_N], y_dist[MAX_N];
lint x_sum[MAX_N], y_sum[MAX_N];
lint find_x_sum(int l, int r) {
    if (!(0 <= l && l < n && 0 <= r && r < n)) return 0;
    if (l > r) return 0;
    return x_sum[r] - ((l == 0) ? 0 : x_sum[l - 1]);
}
lint find_y_sum(int l, int r) {
    if (!(0 <= l && l < n && 0 <= r && r < n)) return 0;
    if (l > r) return 0;
    return y_sum[r] - ((l == 0) ? 0 : y_sum[l - 1]);
}

void precomp() {
    dijk(x);
    for (int i = 0; i <= n - 1; i++) x_dist[i] = min_dist[i];
    dijk(y);
    for (int i = 0; i <= n - 1; i++) y_dist[i] = min_dist[i];

    for (int i = 0; i <= n - 1; i++)
        x_sum[i] = x_dist[i] + ((i == 0) ? 0 : x_sum[i - 1]);
    for (int i = 0; i <= n - 1; i++)
        y_sum[i] = y_dist[i] + ((i == 0) ? 0 : y_sum[i - 1]);
}

int bin_search(int l, int r) {
    int lo = l, hi = r;
    while (lo != hi) {
        int mid = (lo + hi) / 2;
        if (x_dist[mid] >= y_dist[mid]) hi = mid;
        else lo = mid + 1;
    }
    return (x_dist[lo] >= y_dist[lo]) ? lo : r + 1;
}

void init() {
    for (int i = 0; i <= n - 1; i++) {
        adj[i].clear();
    }
}
 
int max_score(int tmp_n, int tmp_x, int tmp_y, lint tmp_k, vector<int> edge1, vector<int> edge2, vector<int> edge3) {
    n = tmp_n;
    x = tmp_x;
    y = tmp_y;
    assert(x < y);
    k = tmp_k;
    init();
    for (int i = 0; i <= n - 2; i++) {
        adj[edge1[i]].push_back({edge2[i], edge3[i]});
        adj[edge2[i]].push_back({edge1[i], edge3[i]});
    }
    precomp();

    int ans = 0;
    for (int x_l = 0; x_l <= n - 1; x_l++) {
        for (int x_r = x_l; x_r <= n - 1; x_r++) {
            for (int y_l = 0; y_l <= n - 1; y_l++) {
                for (int y_r = y_l; y_r <= n - 1; y_r++) {
                    if (!(x_l <= x && x <= x_r)) continue;
                    if (!(y_l <= y && y <= y_r)) continue;
                    if (x_r > y_r || y_l < x_l) continue;

                    if (x_r < y_l) {
                        lint cost = find_x_sum(x_l, x_r) + find_y_sum(y_l, y_r);
                        if (cost > k) continue;
                        ans = max(ans, x_r - x_l + 1 + y_r - y_l + 1);
                        continue;
                    }

                    int i = bin_search(y_l, x_r);
                    lint cost = find_x_sum(x_l, y_l - 1) + find_y_sum(y_l, i - 1) + find_x_sum(i, x_r) + find_y_sum(x_r + 1, y_r);
                    if (cost > k) continue;
                    ans = max(ans, x_r - x_l + 1 + y_r - y_l + 1);
                }
            }
        }
    }

    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