oj.uz

Submission #902638

# Submission time Handle Problem Language Result Execution time Memory
902638 2024-01-10T21:40:00 Z jamesbamber Closing Time (IOI23_closing) C++17
17 / 100
 91 ms 28352 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){
    
    int ct = 0;
    while(pq.size()){
        auto [c, diff, v, prv] = pq.top(); pq.pop();
        if(diff > t or diff == -1) c/=2;
        if(k-c < 0) continue; 
        if(diff == -1){
            k -= c;
            ct++;
            continue;
        }
        if(prv != -1){
            k -= c;
            ct++; 
            if(diff <= t) ct++;
        }
        if(diff > t) pq.push({2*diff, -1, -1, -1});

        for(auto [u, w]: ad[v]){
            if(on_path[u] or u == prv) continue;
            if(diff <= t) pq.push({c+w, diff, u, v});
            else pq.push({(c+w)*2, diff, u, v});
        }
    }
    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;

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

    int ans = greedy(K, X, Y);
    if(tot > K*2) return ans;


    priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<>> pq;
    for(ll t: checkdiff){
        while(pq.size()) pq.pop();
        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({2*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 348 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 25292 KB Output is correct
2 Correct 91 ms 28352 KB Output is correct
3 Correct 47 ms 3036 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 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 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Incorrect 1 ms 348 KB 9th lines differ - on the 1st token, expected: '26', found: '22'
19 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 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 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 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Incorrect 1 ms 348 KB 9th lines differ - on the 1st token, expected: '26', found: '22'
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 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 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 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 1 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 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 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 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 1 ms 348 KB 9th lines differ - on the 1st token, expected: '26', found: '22'
20 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 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 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 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 1 ms 348 KB 9th lines differ - on the 1st token, expected: '26', found: '22'
20 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 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 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 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 1 ms 348 KB 9th lines differ - on the 1st token, expected: '26', found: '22'
20 Halted 0 ms 0 KB -