oj.uz

Submission #840919

# Submission time Handle Problem Language Result Execution time Memory
840919 2023-08-31T22:36:50 Z nicksms Closing Time (IOI23_closing) C++17
43 / 100
 207 ms 54184 KB 
#include "closing.h"
/**
 *      Author:  Nicholas Winschel
 *      Created: 08.31.2023 14:51:13
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
#include <vector>

int max_score(int N, int X, int Y, long long K,
              std::vector<int> u, std::vector<int> v, std::vector<int> W)
{
    // assume cannot/optimal not to reach common vertex
    // overestimates cost in the case that it is possible and optimal
    // swap(u,v);
    ll oK = K;
    V<vi> adj(N);
    for (int i = 0; i < N-1; i++) {
        adj[u[i]].push_back(i);
        adj[v[i]].push_back(i);
    }
    struct op {
        ll c;
        int v, p;
        op () {}
        op(ll c, int v, int p) : c(c), v(v), p(p) {}
        bool operator<(const op b) const {
            return c < b.c;
        }
        bool operator>(const op b) const {
            return c > b.c;
        }
    };
    priority_queue<op, V<op>, greater<op>> pq; 
    pq.emplace(0,X,-1);
    pq.emplace(0,Y,-1);
    int ans1 = 0;
    while (sz(pq)) {
        op e = pq.top();
        pq.pop();
        if (e.c > K) continue;
        K -= e.c;
        ans1++;
        for (int i : adj[e.v]) {
            int x = u[i] == e.v ? v[i] : u[i];
            if (x == e.p) continue;
            pq.emplace(e.c+W[i],x,e.v);
        }
    }
    K = oK;
    vl dist1(N), dist2(N);
    auto dfs = [&](int vv, int p, ll d, vl &a, auto &&dfs) -> void {
        a[vv] = d;
        for (int i : adj[vv]) {
            int x = u[i] == vv ? v[i] : u[i];
            if (x == p) continue;
            dfs(x, vv, d+W[i], a, dfs);
        }
    };
    dfs(X, -1, 0, dist1, dfs);
    dfs(Y, -1, 0, dist2, dfs);
    // for (auto x : dist1) cerr << x << " ";
    //cerr << "\n";
    // for (auto x : dist2) cerr << x << " ";
    //cerr << "\n";
    ll btw = dist2[X];
    V<bool> done(2*N);
    using sins = tuple<ll, int, int>; // cost, op, prev
    using dins = tuple<ll, int, int, int>; // cost, op1, op2, prev
    priority_queue<sins, V<sins>, greater<sins>> q1;
    priority_queue<dins, V<dins>, greater<dins>> q2;
    int ans = 0;
    auto perform = [&](int op, int prev) {
        //cerr << "dbg: " << K << " " << op << " " << prev << "\n";
        int vert = op >= N ? op - N : op;
        assert(!done[op]);
        ans++;
        if ((op < N) != (dist1[vert] <= dist2[vert])) { // NO KIDS
            done[op] = true;
        } else {
            done[op] = true;
            ll cu = abs(dist2[vert]-dist1[vert]);
            q1.emplace(cu, N-(op-vert) + vert, vert); // opposite
            bool b = (dist2[vert] >= dist1[vert]);
            for (int i : adj[vert]) {
                int x = u[i] == vert ? v[i] : u[i];
                if (x == prev) continue;
                if ((dist2[x] >= dist1[x]) != b) continue;
                q1.emplace(min(dist1[x], dist2[x]), x + op - vert, vert); // child
                q2.emplace(max(dist1[x], dist2[x]), x, x+N, vert); // both child
                for (int j : adj[x]) { // this is only OK because we are in a tree...
                    int y = u[j] == x ? v[j] : u[j];
                    if (y == vert) continue;
                    if ((dist2[y] >= dist1[y]) != b) continue;
                    q2.emplace(min(dist1[x], dist2[x]) + min(dist1[y], dist2[y]),
                        x + op - vert,
                        y + op - vert,
                        vert);
                }
            }
        }
    };
    for (int i = 0; i < N; i++) {
        if (dist1[i] + dist2[i] == btw) {
            if (dist1[i] <= dist2[i]) {
                K -= dist1[i];
                perform(i, -1);
            } else {
                K -= dist2[i];
                perform(i + N, -1);
            }
        }
    }
    if (K < 0) return ans1;
    //cerr << "???\n";
    //cerr << sz(q1) << " " << sz(q2) << "\n";
    while (sz(q1) || sz(q2)) {
        while (q2.size()) {
            auto [cu, fi, se, pre] = q2.top();
            if (done[fi] || done[se] || cu > K) {
                //cerr << "popping q2: " << cu << " " << fi << " " << se << " " << pre << "\n";
                q2.pop();
                // //cerr << "Popped q2!\n";
            } else break;
        }
        while (q1.size()) {
            auto [cu, op, pre] = q1.top();
            if (done[op] || cu > K) {
                //cerr << "popping q1: " << cu << " " << op << " " << pre << "\n";
                q1.pop();
                // //cerr << "Popped q1!\n";
            } else break;
        }
        //cerr << "body\n";
        if (q1.size() && !q2.size()) {
            //cerr << "path1\n";
            auto [cu, op, pre] = q1.top();
            q1.pop();
            K -= cu;
            perform(op, pre); 
        } else if (q2.size()) {
            //cerr << "path2\n";
            assert(q1.size());
            auto o1 = q1.top();
            q1.pop();
            while (q1.size()) {
                auto [cu, op, pre] = q1.top();
                if (done[op] || cu > K) {
                    q1.pop();
                } else break;
            }
            auto ob = q2.top();
            if (sz(q1)) { // not given
                auto [cu1, op1, pre1] = o1; 
                auto o2 = q1.top();
                auto [cu2, op2, pre2] = o2;
                // q1.pop();
                auto [cub, fi, se, preb] = ob;
                if (cub <= cu1 + cu2) {
                    q2.pop();
                    K -= cub;
                    perform(fi, preb);
                    perform(se, fi >= N ? fi - N : fi);
                    q1.push(o1);
                    // q1.push(o2);
                } else {
                    K -= cu1;
                    perform(op1, pre1);
                    // q1.push(o2);
                    // q2.push(ob);
                }
            } else {
                q1.push(o1);
                auto [cub, fi, se, preb] = ob;
                q2.pop();
                K -= cub;
                perform(fi, preb);
                perform(se, fi >= N ? fi - N : fi);
            }
        }
    }



    return max(ans, ans1);
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 50464 KB Output is correct
2 Correct 207 ms 54184 KB Output is correct
3 Correct 118 ms 3020 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 232 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 4 ms 1200 KB Output is correct
29 Correct 3 ms 980 KB Output is correct
30 Correct 1 ms 724 KB Output is correct
31 Correct 2 ms 1260 KB Output is correct
32 Correct 2 ms 1260 KB Output is correct

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 232 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 3 ms 340 KB Output is correct
27 Correct 2 ms 724 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 4 ms 1200 KB Output is correct
30 Correct 3 ms 980 KB Output is correct
31 Correct 1 ms 724 KB Output is correct
32 Correct 2 ms 1260 KB Output is correct
33 Correct 2 ms 1260 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 0 ms 212 KB Output is correct
46 Correct 0 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '10', found: '9'
52 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 232 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 3 ms 340 KB Output is correct
27 Correct 2 ms 724 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 4 ms 1200 KB Output is correct
30 Correct 3 ms 980 KB Output is correct
31 Correct 1 ms 724 KB Output is correct
32 Correct 2 ms 1260 KB Output is correct
33 Correct 2 ms 1260 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 0 ms 212 KB Output is correct
46 Correct 0 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '10', found: '9'
52 Halted 0 ms 0 KB -