oj.uz

Submission #843973

# Submission time Handle Problem Language Result Execution time Memory
843973 2023-09-04T18:40:15 Z Lucpp Closing Time (IOI23_closing) C++17
8 / 100
 78 ms 20180 KB 
#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
using ll = long long;

int N, X, Y;
ll maxCost;
vector<vector<pair<int, ll>>> g;

int solveGreedy(){
    priority_queue<tuple<ll, int, int>> pq;
    pq.emplace(0, X, X);
    pq.emplace(0, Y, Y);
    ll remain = maxCost;
    int score = 0;
    while(remain >= 0 && !pq.empty()){
        auto [c, u, p] = pq.top(); pq.pop();
        if(remain + c < 0) break;
        remain += c;
        score++;
        for(auto [v, w] : g[u]){
            if(v != p) pq.emplace(c-w, v, u);
        }
    }
    return score;
}

int max_score(int N_, int X_, int Y_, ll K, vector<int> U, vector<int> V, vector<int> W){
    N = N_, X = X_, Y = Y_, maxCost = K;
    g.clear();
    g.resize(N);
    for(int i = 0; i < N-1; i++){
        g[U[i]].emplace_back(V[i], W[i]);
        g[V[i]].emplace_back(U[i], W[i]);
    }
    return solveGreedy();
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 20060 KB Output is correct
2 Correct 78 ms 20180 KB Output is correct
3 Correct 51 ms 2700 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 496 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -