oj.uz

Submission #966150

# Submission time Handle Problem Language Result Execution time Memory
966150 2024-04-19T12:47:31 Z Boas Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 53244 KB 
#include "closing.h"

#include <vector>
using namespace std;
#include <bits/stdc++.h>
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef set<ii> sii;
typedef vector<sii> vsii;
typedef tuple<int, int, int, bool> item;

#define ALL(x) (x).begin(), x.end()
#define loop(x, i) for (int i = 0; i < x; i++)

void getDist(int i, int d, vi &dist, const vsii &adj)
{
    dist[i] = d;
    for (auto [j, w] : adj[i])
    {
        if (dist[j] != -1)
            continue;
        getDist(j, dist[i] + w, dist, adj);
    }
}

int max_score(int N, int X, int Y, long long K, vi U, vi V, vi W)
{
    vsii adj(N);
    loop(N - 1, i)
    {
        adj[U[i]].insert({V[i], W[i]});
        adj[V[i]].insert({U[i], W[i]});
    }
    vi distX(N, -1), distY(N, -1);
    distX[X] = 0;
    distY[Y] = 0;
    getDist(X, 0, distX, adj);
    getDist(Y, 0, distY, adj);
    priority_queue<item> q;
    for (int i = 0; i < N; i++)
    {
        q.push({-distX[i], -distX[i], i, false});
        q.push({-distY[i], -distY[i], i, true});
    }
    int total = 0;
    vb visX(N), visY(N);
    int score = 0;
    vi time(N, 0);
    while (total <= K && !q.empty())
    {
        auto [oldDiff, d, i, fromY] = q.top();
        q.pop();
        int old = time[i];
        int nieuw = max(-d, time[i]);
        int diff = nieuw - old;
        if (total + diff > K)
            break;
        total += diff;
        time[i] = nieuw;
        score++;
        cerr << "Going to " << i << " from " << (fromY ? 'Y' : 'X') << endl;
        if (fromY)
            visY[i] = 1;
        else
            visX[i] = 1;
        if (!visX[i] && !visY[i])
        {
            int nieuw = max(distY[i], distX[i]);
            int old = fromY ? distY[i] : distX[i];
            int diff = nieuw - old;
            q.push({-diff, fromY ? -distX[i] : -distY[i], i, !fromY});
        }
    }
    cerr << endl;
    return score;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1006 ms 53244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 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 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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