oj.uz

Submission #1070284

# Submission time Handle Problem Language Result Execution time Memory
1070284 2024-08-22T12:46:02 Z zsombor Closing Time (IOI23_closing) C++17
43 / 100
 64 ms 33444 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, x, y, k, ans;
vector<vector<pair<int, ll> > > g(3e5);
vector<vector<ll> > d(2, vector<ll>(3e5, -1));
vector<ll> c(3e5, 0);
vector<vector<bool> > b(2, vector<bool>(3e5, false));
priority_queue<pair<ll, int> > pq;

void reset() {
    for (int i = 0; i < n; i++) {
        g[i].clear();
        d[0][i] = d[1][i] = -1;
        c[i] = 0;
        b[0][i] = b[1][i] = false;
    }
    while (pq.size()) pq.pop();
    ans = 0;
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    x = X;
    y = Y;
    k = K;
    reset();
    for (int i = 0; i < n - 1; i++) {
        g[U[i]].push_back({V[i], W[i]});
        g[V[i]].push_back({U[i], W[i]});
    }
    d[0][x] = d[1][y] = 0;
    pq.push({0, x});
    pq.push({0, y + n});
    while (pq.size()) {
        int i = pq.top().second, j = 0;
        pq.pop();
        if (i >= n) {
            i -= n;
            j++;
        }
        if (b[j][i]) continue;
        if (d[j][i] - c[i] > k) return ans;
        k -= d[j][i] - c[i];
        c[i] = d[j][i];
        b[j][i] = true;
        if (d[1 - j][i] > -1) pq.push({c[i] - d[1 - j][i], (1 - j ? i + n : i)});
        ans++;
        for (auto p: g[i]) {
            ll l = p.first, w = p.second;
            if (d[j][l] > -1) continue;
            d[j][l] = d[j][i] + w;
            int l2 = (j ? l + n : l);
            pq.push({c[l] - d[j][l], l2});
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14644 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 29484 KB Output is correct
2 Correct 64 ms 33444 KB Output is correct
3 Correct 42 ms 19696 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14640 KB Output is correct
2 Correct 5 ms 14644 KB Output is correct
3 Correct 6 ms 14644 KB Output is correct
4 Correct 6 ms 14644 KB Output is correct
5 Correct 6 ms 14644 KB Output is correct
6 Correct 6 ms 14644 KB Output is correct
7 Correct 5 ms 14644 KB Output is correct
8 Correct 5 ms 14644 KB Output is correct
9 Correct 6 ms 14644 KB Output is correct
10 Correct 5 ms 14644 KB Output is correct
11 Correct 5 ms 14644 KB Output is correct
12 Correct 6 ms 14644 KB Output is correct
13 Correct 5 ms 14640 KB Output is correct
14 Correct 7 ms 14644 KB Output is correct
15 Correct 6 ms 14640 KB Output is correct
16 Correct 5 ms 14644 KB Output is correct
17 Correct 5 ms 14512 KB Output is correct
18 Correct 5 ms 14656 KB Output is correct
19 Correct 5 ms 14644 KB Output is correct
20 Correct 5 ms 14640 KB Output is correct
21 Correct 5 ms 14644 KB Output is correct
22 Correct 6 ms 14640 KB Output is correct
23 Correct 5 ms 14640 KB Output is correct
24 Correct 6 ms 14640 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14640 KB Output is correct
2 Correct 5 ms 14644 KB Output is correct
3 Correct 6 ms 14644 KB Output is correct
4 Correct 6 ms 14644 KB Output is correct
5 Correct 6 ms 14644 KB Output is correct
6 Correct 6 ms 14644 KB Output is correct
7 Correct 5 ms 14644 KB Output is correct
8 Correct 5 ms 14644 KB Output is correct
9 Correct 6 ms 14644 KB Output is correct
10 Correct 5 ms 14644 KB Output is correct
11 Correct 5 ms 14644 KB Output is correct
12 Correct 6 ms 14644 KB Output is correct
13 Correct 5 ms 14640 KB Output is correct
14 Correct 7 ms 14644 KB Output is correct
15 Correct 6 ms 14640 KB Output is correct
16 Correct 5 ms 14644 KB Output is correct
17 Correct 5 ms 14512 KB Output is correct
18 Correct 5 ms 14656 KB Output is correct
19 Correct 5 ms 14644 KB Output is correct
20 Correct 5 ms 14640 KB Output is correct
21 Correct 5 ms 14644 KB Output is correct
22 Correct 6 ms 14640 KB Output is correct
23 Correct 5 ms 14640 KB Output is correct
24 Correct 6 ms 14640 KB Output is correct
25 Correct 6 ms 14640 KB Output is correct
26 Correct 7 ms 14660 KB Output is correct
27 Correct 7 ms 14644 KB Output is correct
28 Correct 6 ms 14644 KB Output is correct
29 Correct 7 ms 14644 KB Output is correct
30 Correct 6 ms 14664 KB Output is correct
31 Correct 6 ms 14720 KB Output is correct
32 Correct 7 ms 14640 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14644 KB Output is correct
2 Correct 6 ms 14640 KB Output is correct
3 Correct 5 ms 14644 KB Output is correct
4 Correct 6 ms 14644 KB Output is correct
5 Correct 6 ms 14644 KB Output is correct
6 Correct 6 ms 14644 KB Output is correct
7 Incorrect 5 ms 14640 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14644 KB Output is correct
2 Correct 6 ms 14640 KB Output is correct
3 Correct 5 ms 14644 KB Output is correct
4 Correct 6 ms 14644 KB Output is correct
5 Correct 6 ms 14644 KB Output is correct
6 Correct 6 ms 14644 KB Output is correct
7 Correct 6 ms 14644 KB Output is correct
8 Correct 5 ms 14644 KB Output is correct
9 Correct 5 ms 14644 KB Output is correct
10 Correct 6 ms 14644 KB Output is correct
11 Correct 5 ms 14644 KB Output is correct
12 Correct 5 ms 14644 KB Output is correct
13 Correct 6 ms 14644 KB Output is correct
14 Correct 5 ms 14640 KB Output is correct
15 Correct 7 ms 14644 KB Output is correct
16 Correct 6 ms 14640 KB Output is correct
17 Correct 5 ms 14644 KB Output is correct
18 Correct 5 ms 14512 KB Output is correct
19 Incorrect 5 ms 14640 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
20 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14644 KB Output is correct
2 Correct 6 ms 14640 KB Output is correct
3 Correct 5 ms 14644 KB Output is correct
4 Correct 6 ms 14644 KB Output is correct
5 Correct 6 ms 14644 KB Output is correct
6 Correct 6 ms 14644 KB Output is correct
7 Correct 6 ms 14644 KB Output is correct
8 Correct 5 ms 14644 KB Output is correct
9 Correct 5 ms 14644 KB Output is correct
10 Correct 6 ms 14644 KB Output is correct
11 Correct 5 ms 14644 KB Output is correct
12 Correct 5 ms 14644 KB Output is correct
13 Correct 6 ms 14644 KB Output is correct
14 Correct 5 ms 14640 KB Output is correct
15 Correct 7 ms 14644 KB Output is correct
16 Correct 6 ms 14640 KB Output is correct
17 Correct 5 ms 14644 KB Output is correct
18 Correct 5 ms 14512 KB Output is correct
19 Correct 5 ms 14656 KB Output is correct
20 Correct 5 ms 14644 KB Output is correct
21 Correct 5 ms 14640 KB Output is correct
22 Correct 5 ms 14644 KB Output is correct
23 Correct 6 ms 14640 KB Output is correct
24 Correct 5 ms 14640 KB Output is correct
25 Correct 6 ms 14640 KB Output is correct
26 Incorrect 5 ms 14640 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
27 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14644 KB Output is correct
2 Correct 6 ms 14640 KB Output is correct
3 Correct 5 ms 14644 KB Output is correct
4 Correct 6 ms 14644 KB Output is correct
5 Correct 6 ms 14644 KB Output is correct
6 Correct 6 ms 14644 KB Output is correct
7 Correct 6 ms 14644 KB Output is correct
8 Correct 5 ms 14644 KB Output is correct
9 Correct 5 ms 14644 KB Output is correct
10 Correct 6 ms 14644 KB Output is correct
11 Correct 5 ms 14644 KB Output is correct
12 Correct 5 ms 14644 KB Output is correct
13 Correct 6 ms 14644 KB Output is correct
14 Correct 5 ms 14640 KB Output is correct
15 Correct 7 ms 14644 KB Output is correct
16 Correct 6 ms 14640 KB Output is correct
17 Correct 5 ms 14644 KB Output is correct
18 Correct 5 ms 14512 KB Output is correct
19 Correct 5 ms 14656 KB Output is correct
20 Correct 5 ms 14644 KB Output is correct
21 Correct 5 ms 14640 KB Output is correct
22 Correct 5 ms 14644 KB Output is correct
23 Correct 6 ms 14640 KB Output is correct
24 Correct 5 ms 14640 KB Output is correct
25 Correct 6 ms 14640 KB Output is correct
26 Correct 6 ms 14640 KB Output is correct
27 Correct 7 ms 14660 KB Output is correct
28 Correct 7 ms 14644 KB Output is correct
29 Correct 6 ms 14644 KB Output is correct
30 Correct 7 ms 14644 KB Output is correct
31 Correct 6 ms 14664 KB Output is correct
32 Correct 6 ms 14720 KB Output is correct
33 Correct 7 ms 14640 KB Output is correct
34 Incorrect 5 ms 14640 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14644 KB Output is correct
2 Correct 6 ms 14640 KB Output is correct
3 Correct 5 ms 14644 KB Output is correct
4 Correct 6 ms 14644 KB Output is correct
5 Correct 6 ms 14644 KB Output is correct
6 Correct 6 ms 14644 KB Output is correct
7 Correct 6 ms 14644 KB Output is correct
8 Correct 5 ms 14644 KB Output is correct
9 Correct 5 ms 14644 KB Output is correct
10 Correct 6 ms 14644 KB Output is correct
11 Correct 5 ms 14644 KB Output is correct
12 Correct 5 ms 14644 KB Output is correct
13 Correct 6 ms 14644 KB Output is correct
14 Correct 5 ms 14640 KB Output is correct
15 Correct 7 ms 14644 KB Output is correct
16 Correct 6 ms 14640 KB Output is correct
17 Correct 5 ms 14644 KB Output is correct
18 Correct 5 ms 14512 KB Output is correct
19 Correct 5 ms 14656 KB Output is correct
20 Correct 5 ms 14644 KB Output is correct
21 Correct 5 ms 14640 KB Output is correct
22 Correct 5 ms 14644 KB Output is correct
23 Correct 6 ms 14640 KB Output is correct
24 Correct 5 ms 14640 KB Output is correct
25 Correct 6 ms 14640 KB Output is correct
26 Correct 6 ms 14640 KB Output is correct
27 Correct 7 ms 14660 KB Output is correct
28 Correct 7 ms 14644 KB Output is correct
29 Correct 6 ms 14644 KB Output is correct
30 Correct 7 ms 14644 KB Output is correct
31 Correct 6 ms 14664 KB Output is correct
32 Correct 6 ms 14720 KB Output is correct
33 Correct 7 ms 14640 KB Output is correct
34 Incorrect 5 ms 14640 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -