oj.uz

Submission #894679

# Submission time Handle Problem Language Result Execution time Memory
894679 2023-12-28T16:53:57 Z JeanBombeur Closing Time (IOI23_closing) C++17
52 / 100
 144 ms 47164 KB 
#include "closing.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

//  <|°_°|>

//  M. Broccoli & JeanBombeur

const int MAX_NODES = 2e5;

struct event {
    long long cost;
    int node, id;
};

vector <pair <int, long long>> Adj[MAX_NODES];

long long Dist[2][MAX_NODES];
bool Taken[2][MAX_NODES];

vector <int> Path;

priority_queue <event> Greedy;

bool operator<(event a, event b) {
    return a.cost > b.cost;
}


bool Dfs(int id, int node, int parent = -1, int target = -1) {
    for (pair <int, long long> dest : Adj[node])
    {
        if (dest.first != parent)
        {
            Dist[id][dest.first] = Dist[id][node] + dest.second;
            if (Dfs(id, dest.first, node, target))
                target = node;
        }
    }
    if (node == target)
        Path.push_back(node);
    return node == target;
}

int RunSmart(int answer, long long maxSum) {
    long long last = 0;
    long long sum = 0;
    while (!Greedy.empty())
    {
        auto [cost, node, id] = Greedy.top();
        Greedy.pop();
        if (id == 2)
        {
            if (Taken[0][node] || Taken[1][node])
                continue;
            cost <<= 1;
            if ((sum += cost) <= maxSum)
            {
                answer += 2;
                Taken[0][node] = Taken[1][node] = 1;
            }
            else if (sum - last <= maxSum)
            {
                answer ++;
                break;
            }
            else
                break;
        }
        else
        {
            if (Taken[id][node])
                continue;
            if ((sum += cost) > maxSum)
                break;
            Taken[id][node] = 1;
            answer ++;
            if (!Taken[id ^ 1][node])
                Greedy.push({Dist[id ^ 1][node] - Dist[id][node], node, id ^ 1});
            last = cost;
        }
    }
    return answer;
}

int max_score(int nbNodes, int start1, int start2, long long maxSum,
    vector <int> Left, vector <int> Right, vector <int> Weight) {
    
    maxSum <<= 1;
    
    Path.clear();
    for (int i = 0; i < nbNodes; i ++)
        Adj[i].clear();
    for (int i = 0; i < nbNodes - 1; i ++)
    {
        Adj[Left[i]].emplace_back(Right[i], Weight[i] << 1);
        Adj[Right[i]].emplace_back(Left[i], Weight[i] << 1);
    }
    for (int id = 0; id < 2; id ++)
    {
        fill_n(Dist[id], nbNodes, 0LL);
        fill_n(Taken[id], nbNodes, 0);
        if (!id)
            Dfs(id, start1);
        else
            Dfs(id, start2, -1, start1);
    }
    
    int answer = 0;
    long long sum = 0;
    int greed = 0;
    vector <long long> mini;
    for (int i = 0; i < nbNodes; i ++)
    {
        mini.push_back(Dist[0][i]);
        mini.push_back(Dist[1][i]);
    }
    sort(mini.begin(), mini.end());
    for (long long a : mini)
        if ((sum += a) <= maxSum)
            greed ++;
    
    while (!Greedy.empty())
        Greedy.pop();
    sum = 0;
    for (int a : Path)
    {
        int id = Dist[0][a] > Dist[1][a];
        sum += Dist[id][a];
        answer ++;
        Taken[id][a] = 1;
        Greedy.push({Dist[id ^ 1][a] - Dist[id][a], a, id ^ 1});
    }
    if (sum > maxSum)
        return greed;
    
    for (int i = 0; i < nbNodes; i ++)
    {
        int id = Dist[0][i] > Dist[1][i];
        Greedy.push({Dist[id][i], i, id});
        Greedy.push({Dist[id ^ 1][i] / 2, i, 2});
    }
    
    return max(greed, RunSmart(answer, maxSum - sum));
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 38140 KB Output is correct
2 Correct 144 ms 47164 KB Output is correct
3 Correct 68 ms 11860 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7592 KB Output is correct
5 Correct 2 ms 7588 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7652 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7772 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7592 KB Output is correct
5 Correct 2 ms 7588 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7652 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7772 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 3 ms 8284 KB Output is correct
27 Correct 3 ms 8280 KB Output is correct
28 Correct 3 ms 8540 KB Output is correct
29 Correct 4 ms 8280 KB Output is correct
30 Correct 3 ms 8024 KB Output is correct
31 Correct 3 ms 8284 KB Output is correct
32 Correct 3 ms 8220 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7592 KB Output is correct
6 Correct 2 ms 7588 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7716 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7596 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7592 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7592 KB Output is correct
6 Correct 2 ms 7588 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7652 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7772 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 2 ms 7516 KB Output is correct
26 Correct 2 ms 7516 KB Output is correct
27 Correct 2 ms 7716 KB Output is correct
28 Correct 2 ms 7516 KB Output is correct
29 Correct 2 ms 7516 KB Output is correct
30 Correct 2 ms 7516 KB Output is correct
31 Correct 2 ms 7516 KB Output is correct
32 Correct 2 ms 7596 KB Output is correct
33 Correct 2 ms 7516 KB Output is correct
34 Correct 2 ms 7516 KB Output is correct
35 Correct 2 ms 7516 KB Output is correct
36 Correct 2 ms 7516 KB Output is correct
37 Correct 2 ms 7516 KB Output is correct
38 Correct 2 ms 7592 KB Output is correct
39 Correct 2 ms 7516 KB Output is correct
40 Correct 2 ms 7516 KB Output is correct
41 Correct 2 ms 7516 KB Output is correct
42 Correct 2 ms 7516 KB Output is correct
43 Correct 2 ms 7516 KB Output is correct
44 Correct 2 ms 7512 KB Output is correct
45 Correct 2 ms 7628 KB Output is correct
46 Correct 2 ms 7512 KB Output is correct
47 Correct 2 ms 7516 KB Output is correct
48 Correct 2 ms 7516 KB Output is correct
49 Correct 1 ms 7516 KB Output is correct
50 Correct 2 ms 7516 KB Output is correct
51 Correct 2 ms 7516 KB Output is correct
52 Correct 2 ms 7628 KB Output is correct
53 Correct 2 ms 7516 KB Output is correct
54 Incorrect 2 ms 7516 KB 1st lines differ - on the 1st token, expected: '88', found: '87'
55 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7592 KB Output is correct
6 Correct 2 ms 7588 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7652 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7772 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 2 ms 7516 KB Output is correct
26 Correct 3 ms 7516 KB Output is correct
27 Correct 3 ms 8284 KB Output is correct
28 Correct 3 ms 8280 KB Output is correct
29 Correct 3 ms 8540 KB Output is correct
30 Correct 4 ms 8280 KB Output is correct
31 Correct 3 ms 8024 KB Output is correct
32 Correct 3 ms 8284 KB Output is correct
33 Correct 3 ms 8220 KB Output is correct
34 Correct 2 ms 7516 KB Output is correct
35 Correct 2 ms 7716 KB Output is correct
36 Correct 2 ms 7516 KB Output is correct
37 Correct 2 ms 7516 KB Output is correct
38 Correct 2 ms 7516 KB Output is correct
39 Correct 2 ms 7516 KB Output is correct
40 Correct 2 ms 7596 KB Output is correct
41 Correct 2 ms 7516 KB Output is correct
42 Correct 2 ms 7516 KB Output is correct
43 Correct 2 ms 7516 KB Output is correct
44 Correct 2 ms 7516 KB Output is correct
45 Correct 2 ms 7516 KB Output is correct
46 Correct 2 ms 7592 KB Output is correct
47 Correct 2 ms 7516 KB Output is correct
48 Correct 2 ms 7516 KB Output is correct
49 Correct 2 ms 7516 KB Output is correct
50 Correct 2 ms 7516 KB Output is correct
51 Correct 2 ms 7516 KB Output is correct
52 Correct 2 ms 7512 KB Output is correct
53 Correct 2 ms 7628 KB Output is correct
54 Correct 2 ms 7512 KB Output is correct
55 Correct 2 ms 7516 KB Output is correct
56 Correct 2 ms 7516 KB Output is correct
57 Correct 1 ms 7516 KB Output is correct
58 Correct 2 ms 7516 KB Output is correct
59 Correct 2 ms 7516 KB Output is correct
60 Correct 2 ms 7628 KB Output is correct
61 Correct 2 ms 7516 KB Output is correct
62 Incorrect 2 ms 7516 KB 1st lines differ - on the 1st token, expected: '88', found: '87'
63 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7592 KB Output is correct
6 Correct 2 ms 7588 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7652 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7516 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7772 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 2 ms 7516 KB Output is correct
26 Correct 3 ms 7516 KB Output is correct
27 Correct 3 ms 8284 KB Output is correct
28 Correct 3 ms 8280 KB Output is correct
29 Correct 3 ms 8540 KB Output is correct
30 Correct 4 ms 8280 KB Output is correct
31 Correct 3 ms 8024 KB Output is correct
32 Correct 3 ms 8284 KB Output is correct
33 Correct 3 ms 8220 KB Output is correct
34 Correct 2 ms 7516 KB Output is correct
35 Correct 2 ms 7716 KB Output is correct
36 Correct 2 ms 7516 KB Output is correct
37 Correct 2 ms 7516 KB Output is correct
38 Correct 2 ms 7516 KB Output is correct
39 Correct 2 ms 7516 KB Output is correct
40 Correct 2 ms 7596 KB Output is correct
41 Correct 2 ms 7516 KB Output is correct
42 Correct 2 ms 7516 KB Output is correct
43 Correct 2 ms 7516 KB Output is correct
44 Correct 2 ms 7516 KB Output is correct
45 Correct 2 ms 7516 KB Output is correct
46 Correct 2 ms 7592 KB Output is correct
47 Correct 2 ms 7516 KB Output is correct
48 Correct 2 ms 7516 KB Output is correct
49 Correct 2 ms 7516 KB Output is correct
50 Correct 2 ms 7516 KB Output is correct
51 Correct 2 ms 7516 KB Output is correct
52 Correct 2 ms 7512 KB Output is correct
53 Correct 2 ms 7628 KB Output is correct
54 Correct 2 ms 7512 KB Output is correct
55 Correct 2 ms 7516 KB Output is correct
56 Correct 2 ms 7516 KB Output is correct
57 Correct 1 ms 7516 KB Output is correct
58 Correct 2 ms 7516 KB Output is correct
59 Correct 2 ms 7516 KB Output is correct
60 Correct 2 ms 7628 KB Output is correct
61 Correct 2 ms 7516 KB Output is correct
62 Incorrect 2 ms 7516 KB 1st lines differ - on the 1st token, expected: '88', found: '87'
63 Halted 0 ms 0 KB -