oj.uz

Submission #1081217

# Submission time Handle Problem Language Result Execution time Memory
1081217 2024-08-29T19:48:10 Z ArthuroWich Closing Time (IOI23_closing) C++17
43 / 100
 78 ms 32852 KB 
#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
vector<pair<int, int>> adj[200005];
int32_t solve1234(int32_t n, int32_t X, int32_t Y, int k) {
    int ans = 0;
    vector<int> vis(n, 0), distx(n, -1), disty(n, -1);
    set<tuple<int, int, int>> pq; // let 0 be x, 1 be y
    distx[X] = 0;
    disty[Y] = 0;
    pq.insert({0, X, 0});
    pq.insert({0, Y, 1});
    while(!pq.empty()) {
        auto [d, a, ind] = *pq.begin();
        pq.erase(*pq.begin());
        if (vis[a] == 0 && distx[a] != -1 && disty[a] != -1) {
            if (ind == 0) {
                if (pq.count({disty[a], a, 1})) {
                    pq.erase({disty[a], a, 1});
                    pq.insert({disty[a]-distx[a], a, 1});
                }
            } else {
                if (pq.count({distx[a], a, 0})) {
                    pq.erase({distx[a], a, 0});
                    pq.insert({distx[a]-disty[a], a, 0});
                }
            }
        }
        vis[a] = d;
        if (k < d) {
            break;
        } else {
            k -= d;
            ans++;
        }
        if (ind == 0) {
            for (auto [b, w] : adj[a]) {
                if (distx[b] != -1) {
                    continue;
                }
                distx[b] = distx[a]+w;
                if (vis[b] >= distx[b]) {
                    pq.insert({0, b, 0});
                } else {
                    pq.insert({(distx[b]-vis[b]), b, 0});
                }
            }
        } else {
            for (auto [b, w] : adj[a]) {
                if (disty[b] != -1) {
                    continue;
                }
                disty[b] = disty[a]+w;
                if (vis[b] >= disty[b]) {
                    pq.insert({0, b, 1});
                } else {
                    pq.insert({(disty[b]-vis[b]), b, 1});
                }
            }
        }
    }
    return ans;
}
int32_t max_score(int32_t n, int32_t X, int32_t Y, int k, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
    int ans = 0, temp = 0;
    vector<int> vis(n, 0), distx(n, -1), disty(n, -1), csing(n, 0), cmult(n, 0);
    for (int i = 0; i < n; i++) {
        adj[i].clear();
    }
    for (int i = 0; i < n-1; i++) {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    temp = solve1234(n, X, Y, k); // subtask 1, 2, 3, 4, it works
    set<pair<int, int>> pq, pqex, pqf; // for normal, for disgusting cases, for last check 
    distx[X] = 0;
    disty[Y] = 0;
    queue<int> q;
    q.push(X);
    while(!q.empty()) {
        int a = q.front();
        q.pop();
        for (auto [b, w] : adj[a]) {
            if (distx[b] == -1) {
                distx[b] = distx[a]+w;
                q.push(b);
            }
        }
    }
    q.push(Y);
    while(!q.empty()) {
        int a = q.front();
        q.pop();
        for (auto [b, w] : adj[a]) {
            if (disty[b] == -1) {
                disty[b] = disty[a]+w;
                q.push(b);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        csing[i] = min(distx[i], disty[i]); // x take or y take
        cmult[i] = max(distx[i], disty[i])-csing[i]; // both take
    }
    // best is to take all on path except not but that is checked by my 1st attempt
    for (int i = 0; i < n; i++) {
        if (distx[i]+disty[i] == distx[Y] && csing[i] <= k) {
            k -= csing[i];
            ans++;
            pq.insert({cmult[i], i});
        } else if (distx[i]+disty[i] == distx[Y] && csing[i] > k) {
            return temp;
        }
    }
    for (int i = 0; i < n; i++) {
        if (distx[i]+disty[i] == distx[Y]) {
            continue;
        }
        if (csing[i] > cmult[i]) {
            pqex.insert({csing[i]+cmult[i], i});
            pqf.insert({csing[i], i});
        } else {
            pq.insert({csing[i], i});
            pq.insert({cmult[i], i});
        }
    }
    while(pq.size() > 1 && !pqex.empty()) {
        auto [a, i1] = *pq.begin();
        pq.erase(pq.begin());
        auto [b, i2] = *pq.begin();
        pq.erase(pq.begin());
        auto [c, i3] = *pqex.begin();
        pqex.erase(pqex.begin());
        if (min(a, c) > k) {
            pq.insert({a, i1});
            pq.insert({b, i2});
            pqex.insert({c, i3});
            break;
        }
        if (a+b < c) {
            k -= a;
            ans++;
            pqex.insert({c, i3});
        } else {
            k -= c;
            vis[i3] = 1;
            ans += 2;
            pq.insert({a, i1});
            pq.insert({b, i2});
        }
    }
    while(!pqex.empty()) {
        auto [a, i1] = *pqex.begin();
        pqex.erase(pqex.begin());
        if (a > k) {
            break;
        } else {
            k -= a;
            vis[i1] = 1;
            ans += 2;
        }
    }
    while(!pq.empty()) {
        auto [a, i1] = *pq.begin();
        pq.erase(pq.begin());
        if (a > k) {
            break;
        } else {
            k -= a;
            ans++;
        }
    }
    while(!pqf.empty()) {
        auto [a, i1] = *pqf.begin();
        pqf.erase(pqf.begin());
        if (vis[i1]) {
            continue;
        }
        if (a > k) {
            break;
        } else {
            k -= a;
            ans++;
        }
    }
    return max(temp, ans);
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 32592 KB Output is correct
2 Correct 74 ms 32852 KB Output is correct
3 Correct 41 ms 7516 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 2 ms 4956 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 4956 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 3 ms 5212 KB Output is correct
20 Correct 2 ms 5212 KB Output is correct
21 Correct 2 ms 5212 KB Output is correct
22 Correct 3 ms 4952 KB Output is correct
23 Correct 2 ms 4956 KB Output is correct
24 Correct 3 ms 4960 KB Output is correct
25 Correct 4 ms 4956 KB Output is correct
26 Correct 4 ms 5640 KB Output is correct
27 Correct 3 ms 5724 KB Output is correct
28 Correct 3 ms 5568 KB Output is correct
29 Correct 3 ms 5464 KB Output is correct
30 Correct 3 ms 5468 KB Output is correct
31 Correct 3 ms 5468 KB Output is correct
32 Correct 3 ms 5468 KB Output is correct

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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