oj.uz

Submission #940509

# Submission time Handle Problem Language Result Execution time Memory
940509 2024-03-07T10:07:55 Z Ghetto Closing Time (IOI23_closing) C++17
9 / 100
 1000 ms 31596 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 31596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 7 ms 12988 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 5 ms 12892 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 7 ms 12988 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 5 ms 12892 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 32 ms 12892 KB Output is correct
13 Correct 32 ms 12964 KB Output is correct
14 Correct 41 ms 12892 KB Output is correct
15 Correct 41 ms 12892 KB Output is correct
16 Correct 25 ms 12988 KB Output is correct
17 Correct 27 ms 12888 KB Output is correct
18 Correct 6 ms 12892 KB Output is correct
19 Execution timed out 1068 ms 12892 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 7 ms 12988 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 6 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 5 ms 12892 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 32 ms 12892 KB Output is correct
13 Correct 32 ms 12964 KB Output is correct
14 Correct 41 ms 12892 KB Output is correct
15 Correct 41 ms 12892 KB Output is correct
16 Correct 25 ms 12988 KB Output is correct
17 Correct 27 ms 12888 KB Output is correct
18 Correct 6 ms 12892 KB Output is correct
19 Execution timed out 1068 ms 12892 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -