oj.uz

Submission #902566

# Submission time Handle Problem Language Result Execution time Memory
902566 2024-01-10T18:06:25 Z jamesbamber Closing Time (IOI23_closing) C++17
9 / 100
 1000 ms 33768 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<vector<pair<int,ll>>> ad;
vector<int> on_path;
int n;

vector<pair<int, ll>> find_path(int s, int e){
    
    vector<pair<int, ll>> prv(n, {-1, -1});

    queue<int> q; q.push(e);
    while(q.size()){
        int v = q.front(); q.pop();
        for(auto [u, w]: ad[v]){
            if(u == prv[v].first) continue;
            prv[u] = {v, w};
            q.push(u);
        }
    }
    vector<pair<int, ll>> path; 
    pair<int, ll> v = {s, 0};
    while(v.first != -1){
        path.push_back(v);
        v = prv[v.first];
    }
    return path;
}   

int calc_sus(ll k, ll t, priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq){

    priority_queue<ll, vector<ll>, greater<>> stuff;
    
    int ct = 0;
    while(pq.size()){
        auto [c, diff, v, prv] = pq.top(); pq.pop();
        if(k-c < 0) return ct; 
        if(prv != -1){
            k -= c;
            ct++; 
            if(diff <= t) ct++;
        }
        if(diff > t) stuff.push(diff);

        for(auto [u, w]: ad[v]){
            if(on_path[u] or u == prv) continue;
            pq.push({c+w, diff, u, v});
        }
    }
    while(stuff.size()){
        int c = stuff.top(); stuff.pop();
        if(k-c < 0) return ct;
        k -= c;
        ct++;
    }
    return ct;
}

int greedy(ll k, int s1, int s2){
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<>> pq;
    pq.push({0, s1, -1}); pq.push({0, s2, -1});
    int ct = 0;
    while(pq.size()){
        auto [c, v, prv] = pq.top(); pq.pop();
        if(k-c < 0) return ct;
        k -= c; ct++;

        for(auto [u, w]: ad[v]){
            if(u == prv) continue;
            pq.push({c+w, u, v});
        }
    }
    return ct;
}

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n = N;
    ad.assign(N, vector<pair<int,ll>>());
    for(int i=0; i<N-1; i++){
        ad[U[i]].push_back({V[i], W[i]});
        ad[V[i]].push_back({U[i], W[i]});
    }

    vector<pair<int, ll>> path = find_path(X, Y);
    on_path.assign(N, 0); for(auto [a, b]: path) on_path[a] = 1;
    vector<ll> diff(N), dist(N);

    ll tot = 0, sum = 0;
    for(auto [a, b]: path) tot += b;

    vector<ll> checkdiff; checkdiff.push_back(0);
    for(auto [a, b]: path){
        sum += b;
        diff[a] = abs(2*sum - tot);
        dist[a] = min(sum, tot-sum);
        checkdiff.push_back(diff[a]);
    }

    int ans = greedy(K, X, Y);
    if(dist[X] > 2*K) return ans;
    for(ll t: checkdiff){
        priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;
        ll k = K;
        int ct = 0;
        for(auto [c, d]: path){
            if(diff[c] <= t) pq.push({dist[c]+diff[c], diff[c], c, -1}), ct+=2, k-= dist[c]+diff[c];
            else pq.push({dist[c], diff[c], c, -1}), ct++, k-= dist[c];
        }
        if(k < 0) continue;
        ans = max(ans, ct + calc_sus(k, t, pq));
    }

    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '173', found: '172'
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '173', found: '172'
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 600 KB Output is correct
13 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '173', found: '172'
14 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 600 KB Output is correct
13 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '173', found: '172'
14 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 600 KB Output is correct
13 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '173', found: '172'
14 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 600 KB Output is correct
13 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '173', found: '172'
14 Halted 0 ms 0 KB -