oj.uz

Submission #840767

# Submission time Handle Problem Language Result Execution time Memory
840767 2023-08-31T16:50:53 Z vjudge1 Closing Time (IOI23_closing) C++17
43 / 100
 704 ms 40160 KB 
#include "closing.h"

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> adj[200000];

void dfs(int u, int p, vector<int64_t>& d) {
        for (auto [v, c] : adj[u]) {
                if (v == p) continue;
                d[v] = d[u] + c;
                dfs(v, u, d);
        }
}

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
        for (int i = 0; i < N; i++) adj[i].clear();
        for (int i = 0; i < N - 1; i++) {
                adj[U[i]].emplace_back(V[i], W[i]);
                adj[V[i]].emplace_back(U[i], W[i]);
        }
        vector<int64_t> dX(N), dY(N);
        dfs(X, -1, dX);
        dfs(Y, -1, dY);
        vector<int> ord(N);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
                return max(dX[i], dY[i]) < max(dX[j], dY[j]);
        });
        vector<int> path;
        for (int i = 0; i < N; i++) {
                if (dX[i] + dY[i] == dX[Y]) path.emplace_back(i);
        }
        vector<int> both(N, 0);
        int64_t cur = 0;

        auto solve = [&](bool con = 1) {
                if (cur > K) return -N * 2;
                int cnt = 0;
                int64_t cost = cur;
                vector<int> c(N, 0);
                if (con) {
                        for (int x : path) {
                                if (both[x]) continue;
                                cost += min(dX[x], dY[x]);
                                c[x] = 1;
                                cnt++;
                        }
                        if (cost > K) return -N * 2;
                }
                priority_queue<pair<int64_t, int>> pq;
                for (int i = 0; i < N; i++) {
                        if (both[i]) continue;
                        if (c[i]) continue;
                        pq.emplace(-dX[i], i);
                        pq.emplace(-dY[i], i);
                }
                while (pq.size()) {
                        auto [v, i] = pq.top();
                        pq.pop();
                        if (c[i]) continue;
                        if (cost - v > K) break;
                        cnt++;
                        cost -= v;
                        c[i] = 1;
                }
                return cnt;
        };

        int res = solve(0);
        for (int i = 0; i < N; i++) {
                both[ord[i]] = 1;
                cur += max(dX[ord[i]], dY[ord[i]]);
                res = max(res, solve() + i * 2 + 2);
        }
        return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 35480 KB Output is correct
2 Correct 157 ms 40160 KB Output is correct
3 Correct 79 ms 7500 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 4 ms 4976 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 17 ms 5084 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 7 ms 5076 KB Output is correct
22 Correct 2 ms 5076 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 2 ms 5076 KB Output is correct
25 Correct 7 ms 4948 KB Output is correct
26 Correct 704 ms 5588 KB Output is correct
27 Correct 5 ms 5572 KB Output is correct
28 Correct 32 ms 5588 KB Output is correct
29 Correct 399 ms 5588 KB Output is correct
30 Correct 3 ms 5460 KB Output is correct
31 Correct 10 ms 5588 KB Output is correct
32 Correct 10 ms 5588 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Incorrect 2 ms 4948 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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 4 ms 4976 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Incorrect 2 ms 4948 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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 4 ms 4976 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 17 ms 5084 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Correct 7 ms 5076 KB Output is correct
23 Correct 2 ms 5076 KB Output is correct
24 Correct 3 ms 5076 KB Output is correct
25 Correct 2 ms 5076 KB Output is correct
26 Incorrect 2 ms 4948 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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 4 ms 4976 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 17 ms 5084 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Correct 7 ms 5076 KB Output is correct
23 Correct 2 ms 5076 KB Output is correct
24 Correct 3 ms 5076 KB Output is correct
25 Correct 2 ms 5076 KB Output is correct
26 Correct 7 ms 4948 KB Output is correct
27 Correct 704 ms 5588 KB Output is correct
28 Correct 5 ms 5572 KB Output is correct
29 Correct 32 ms 5588 KB Output is correct
30 Correct 399 ms 5588 KB Output is correct
31 Correct 3 ms 5460 KB Output is correct
32 Correct 10 ms 5588 KB Output is correct
33 Correct 10 ms 5588 KB Output is correct
34 Incorrect 2 ms 4948 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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 4 ms 4976 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 17 ms 5084 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Correct 7 ms 5076 KB Output is correct
23 Correct 2 ms 5076 KB Output is correct
24 Correct 3 ms 5076 KB Output is correct
25 Correct 2 ms 5076 KB Output is correct
26 Correct 7 ms 4948 KB Output is correct
27 Correct 704 ms 5588 KB Output is correct
28 Correct 5 ms 5572 KB Output is correct
29 Correct 32 ms 5588 KB Output is correct
30 Correct 399 ms 5588 KB Output is correct
31 Correct 3 ms 5460 KB Output is correct
32 Correct 10 ms 5588 KB Output is correct
33 Correct 10 ms 5588 KB Output is correct
34 Incorrect 2 ms 4948 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -