oj.uz

Submission #891341

# Submission time Handle Problem Language Result Execution time Memory
891341 2023-12-22T19:11:50 Z Maaxle Closing Time (IOI23_closing) C++17
17 / 100
 98 ms 26596 KB 
#include "closing.h"
#include <bits/stdc++.h>
    
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 ((ll) 1 << 30)
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue
    
using namespace std;
    
vector<vector<pair<ll, ll>>> adj;
vector<ll> memo;

struct TPos {
    ll i, wth = -INF64, from;

    string toString() {
        return to_string(i) + ":" + to_string(wth) + ":" + to_string(from);
    }
};
bool operator < (const TPos& a, const TPos& b) {
    return (a.wth - memo[a.i] > b.wth - memo[b.i]);
}
bool operator == (const TPos& a, const TPos& b) {
    return (a.i == b.i && a.from == b.from && a.wth == b.wth);
}

vector<TPos> fut;

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    adj.clear();
    adj.resize(N);
    
    memo.clear();
    memo.resize(N);

    fut.clear();
    fut.resize(N);

    range(i, 0, N - 1){
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    
    pqueue<TPos> pq;
    pq.push({X, 0, X});
    fut[X] = {X, 0, X};
    pq.push({Y, 0, Y});
    fut[Y] = {Y, 0, Y};

    ll ans = 0;
    ll sum = 0;
    TPos t;
    while (!pq.empty()) {
        t = pq.top(); pq.pop();
        if (fut[t.i].wth == -INF64) continue;
        if (t == fut[t.i]) fut[t.i].wth = -INF64;

        ll dif = t.wth - memo[t.i];
        if (sum + dif > K) break;

        // cout << t.toString() << "  |  ";

        memo[t.i] = t.wth;
        if (fut[t.i].wth != -INF64)
            pq.push(fut[t.i]);

        for (pair<ll, ll> a : adj[t.i]) {
            if (a.first != t.from) {
                pq.push({a.first, t.wth + a.second, t.i});
                if (t.wth + a.second >= fut[a.first].wth) {
                    fut[a.first] = {a.first, t.wth + a.second, t.i};
                }
            }
        }

        // range(i, 0, N) cout << "[ " << fut[i].toString() << " ] ";
        // cout << '\n';

        ans++;
        sum += dif;
    }

    // cout << "----------------\n";
    
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 26448 KB Output is correct
2 Correct 85 ms 26596 KB Output is correct
3 Correct 57 ms 2904 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 500 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 0 ms 348 KB 23rd lines differ - on the 1st token, expected: '32', found: '31'
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 500 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 0 ms 348 KB 23rd lines differ - on the 1st token, expected: '32', found: '31'
19 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 348 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 348 KB Output is correct
6 Correct 0 ms 344 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 348 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 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 500 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
20 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 348 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 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 500 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB 23rd lines differ - on the 1st token, expected: '32', found: '31'
20 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 348 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 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 500 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB 23rd lines differ - on the 1st token, expected: '32', found: '31'
20 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 348 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 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 500 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB 23rd lines differ - on the 1st token, expected: '32', found: '31'
20 Halted 0 ms 0 KB -