oj.uz

Submission #847279

# Submission time Handle Problem Language Result Execution time Memory
847279 2023-09-09T11:12:27 Z sebinkim Closing Time (IOI23_closing) C++17
43 / 100
 156 ms 47480 KB 
#include "closing.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

vector<pll> T[202020];
ll X[202020], Y[202020];
int n; ll l;

void dfs(int u, int p, ll *X) {
    for (auto &[v, w]: T[u]) if (v != p) {
        X[v] = X[u] + w;
        dfs(v, u, X);
    }
}

int solve1(ll k) {
    vector<ll> V;
    int i;
    for (i = 0; i < n; i++) {
        V.push_back(X[i]);
        V.push_back(Y[i]);
    }
    sort(V.begin(), V.end());
    for (i = 0; i < n + n; i++) {
        k -= V[i];
        if (k < 0) break;
    }
    return i;
}

ll D[6060];
int solve2(ll k) {
    priority_queue<pll> P01, P02, P10, P12, P21;
    vector<ll> C(n, 0);
    int i;

    for (i = 0; i < n; i++) {
        if (X[i] > Y[i]) swap(X[i], Y[i]);
        if (X[i] + Y[i] == l) {
            k -= X[i]; Y[i] -= X[i]; X[i] = 0;
        }
        Y[i] -= X[i];

        P01.emplace(-X[i], i);
        P02.emplace(-X[i] - Y[i], i);
    }
    if (k < 0) return 0;

    for (i = 0; i < n + n; i++) {
        ll m = -1e18; int f;

        for (; !P01.empty() && C[P01.top().second] != 0; P01.pop());
        for (; !P02.empty() && C[P02.top().second] != 0; P02.pop());
        for (; !P10.empty() && C[P10.top().second] != 1; P10.pop());
        for (; !P12.empty() && C[P12.top().second] != 1; P12.pop());
        for (; !P21.empty() && C[P21.top().second] != 1; P21.pop());

        if (!P01.empty()) {
            auto [t, _] = P01.top();
            if (m < t) m = t, f = 1;
        }
        if (!P12.empty()) {
            auto [t, _] = P12.top();
            if (m < t) m = t, f = 2;
        }
        if (!P10.empty() && !P02.empty()) {
            auto [t1, _] = P10.top();
            auto [t2, __] = P02.top();
            ll t = t1 + t2;
            if (m < t) m = t, f = 3;
        }
        if (!P21.empty() && !P02.empty()) {
            auto [t1, _] = P21.top();
            auto [t2, __] = P02.top();
            ll t = t1 + t2;
            if (m < t) m = t, f = 4;
        }

        k += m;
        if (k < 0) break;

        if (f == 1) {
            auto [t, j] = P01.top(); P01.pop();
            P10.emplace(X[j], j);
            P12.emplace(-Y[j], j);
            C[j] = 1;
        } else if (f == 2) {
            auto [t, j] = P12.top(); P12.pop();
            P21.emplace(Y[j], j);
            C[j] = 2;
        } else if (f == 3) {
            auto [t1, j1] = P10.top(); P10.pop();
            P01.emplace(-X[j1], j1);
            P02.emplace(-X[j1] - Y[j1], j1);
            C[j1] = 0;

            auto [t2, j2] = P02.top(); P02.pop();
            C[j2] = 2;
        } else if (f == 4) {
            auto [t1, j1] = P21.top(); P21.pop();
            P01.emplace(-X[j1], j1);
            P02.emplace(-X[j1] - Y[j1], j1);
            C[j1] = 1;

            auto [t2, j2] = P02.top(); P02.pop();
            P21.emplace(Y[j2], j2);
            C[j2] = 2;
        }
    }

    return i;
}

int max_score(int n, int x, int y, ll k, vector<int> U, vector<int> V, vector<int> W) {
    ::n = n;
    int i;
    for (i = 0; i < n; i++) {
        T[i].clear();
    }
    for (i = 0; i < n - 1; i++) {
        T[U[i]].emplace_back(V[i], W[i]);
        T[V[i]].emplace_back(U[i], W[i]);
    }
    X[x] = Y[y] = 0;
    dfs(x, x, X); dfs(y, y, Y);
    l = X[y];

    int a = solve1(k);
    a = max(a, solve2(k));

    return a;
}

Compilation message

closing.cpp: In function 'int solve2(ll)':
closing.cpp:94:16: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |         } else if (f == 3) {
      |                ^~

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 41744 KB Output is correct
2 Correct 156 ms 47480 KB Output is correct
3 Correct 70 ms 10832 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8180 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8024 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8228 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8024 KB Output is correct
19 Correct 3 ms 8284 KB Output is correct
20 Correct 2 ms 8536 KB Output is correct
21 Correct 2 ms 8284 KB Output is correct
22 Correct 2 ms 8284 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 2 ms 8440 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8180 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8024 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8228 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8024 KB Output is correct
19 Correct 3 ms 8284 KB Output is correct
20 Correct 2 ms 8536 KB Output is correct
21 Correct 2 ms 8284 KB Output is correct
22 Correct 2 ms 8284 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 2 ms 8440 KB Output is correct
25 Correct 3 ms 8028 KB Output is correct
26 Correct 4 ms 8796 KB Output is correct
27 Correct 3 ms 8540 KB Output is correct
28 Correct 4 ms 8796 KB Output is correct
29 Correct 4 ms 8792 KB Output is correct
30 Correct 3 ms 8540 KB Output is correct
31 Correct 3 ms 8796 KB Output is correct
32 Correct 3 ms 8796 KB Output is correct

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8180 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8024 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8228 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8028 KB Output is correct
19 Correct 2 ms 8024 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 2 ms 8536 KB Output is correct
22 Correct 2 ms 8284 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 2 ms 8284 KB Output is correct
25 Correct 2 ms 8440 KB Output is correct
26 Correct 2 ms 8028 KB Output is correct
27 Correct 3 ms 8028 KB Output is correct
28 Correct 2 ms 8028 KB Output is correct
29 Correct 2 ms 8028 KB Output is correct
30 Correct 2 ms 8028 KB Output is correct
31 Correct 2 ms 8028 KB Output is correct
32 Correct 2 ms 8028 KB Output is correct
33 Correct 3 ms 8024 KB Output is correct
34 Correct 2 ms 8028 KB Output is correct
35 Correct 2 ms 8028 KB Output is correct
36 Correct 2 ms 8028 KB Output is correct
37 Correct 2 ms 8028 KB Output is correct
38 Correct 2 ms 8028 KB Output is correct
39 Correct 2 ms 8028 KB Output is correct
40 Incorrect 2 ms 8028 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
41 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8180 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8024 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8228 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8028 KB Output is correct
19 Correct 2 ms 8024 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 2 ms 8536 KB Output is correct
22 Correct 2 ms 8284 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 2 ms 8284 KB Output is correct
25 Correct 2 ms 8440 KB Output is correct
26 Correct 3 ms 8028 KB Output is correct
27 Correct 4 ms 8796 KB Output is correct
28 Correct 3 ms 8540 KB Output is correct
29 Correct 4 ms 8796 KB Output is correct
30 Correct 4 ms 8792 KB Output is correct
31 Correct 3 ms 8540 KB Output is correct
32 Correct 3 ms 8796 KB Output is correct
33 Correct 3 ms 8796 KB Output is correct
34 Correct 2 ms 8028 KB Output is correct
35 Correct 3 ms 8028 KB Output is correct
36 Correct 2 ms 8028 KB Output is correct
37 Correct 2 ms 8028 KB Output is correct
38 Correct 2 ms 8028 KB Output is correct
39 Correct 2 ms 8028 KB Output is correct
40 Correct 2 ms 8028 KB Output is correct
41 Correct 3 ms 8024 KB Output is correct
42 Correct 2 ms 8028 KB Output is correct
43 Correct 2 ms 8028 KB Output is correct
44 Correct 2 ms 8028 KB Output is correct
45 Correct 2 ms 8028 KB Output is correct
46 Correct 2 ms 8028 KB Output is correct
47 Correct 2 ms 8028 KB Output is correct
48 Incorrect 2 ms 8028 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
49 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8180 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8024 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8228 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8028 KB Output is correct
19 Correct 2 ms 8024 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 2 ms 8536 KB Output is correct
22 Correct 2 ms 8284 KB Output is correct
23 Correct 2 ms 8284 KB Output is correct
24 Correct 2 ms 8284 KB Output is correct
25 Correct 2 ms 8440 KB Output is correct
26 Correct 3 ms 8028 KB Output is correct
27 Correct 4 ms 8796 KB Output is correct
28 Correct 3 ms 8540 KB Output is correct
29 Correct 4 ms 8796 KB Output is correct
30 Correct 4 ms 8792 KB Output is correct
31 Correct 3 ms 8540 KB Output is correct
32 Correct 3 ms 8796 KB Output is correct
33 Correct 3 ms 8796 KB Output is correct
34 Correct 2 ms 8028 KB Output is correct
35 Correct 3 ms 8028 KB Output is correct
36 Correct 2 ms 8028 KB Output is correct
37 Correct 2 ms 8028 KB Output is correct
38 Correct 2 ms 8028 KB Output is correct
39 Correct 2 ms 8028 KB Output is correct
40 Correct 2 ms 8028 KB Output is correct
41 Correct 3 ms 8024 KB Output is correct
42 Correct 2 ms 8028 KB Output is correct
43 Correct 2 ms 8028 KB Output is correct
44 Correct 2 ms 8028 KB Output is correct
45 Correct 2 ms 8028 KB Output is correct
46 Correct 2 ms 8028 KB Output is correct
47 Correct 2 ms 8028 KB Output is correct
48 Incorrect 2 ms 8028 KB 1st lines differ - on the 1st token, expected: '26', found: '25'
49 Halted 0 ms 0 KB -