oj.uz

Submission #957338

# Submission time Handle Problem Language Result Execution time Memory
957338 2024-04-03T14:02:25 Z jamesbamber Closing Time (IOI23_closing) C++17
8 / 100
 118 ms 41040 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

void dfs(int v, int p){
    for(auto [u, w]: ad[v]){
        if(u == p) continue;
        prv[u] = v;
        dist[u] = dist[v]+w;
        dfs(u, v);
    }
}

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]});
    }

    dist.assign(n, 0); prv.assign(n, -1); on_path.assign(n, 0);

    dfs(X, -1);
    int curr = Y, path_sz = 0;
    while(curr != -1){
        on_path[curr] = 1; path_sz++;
        curr = prv[curr];
    }

    vector<ll> distX = dist;
    dist.assign(n, 0); dfs(Y, -1);
    vector<ll> distY = dist;

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

    vector dp(n+1, vector<ll>(2*n+1, 1e18+1));

    dp[0][path_sz] = 0;
    for(int i=0; i<n; i++){
        if(!on_path[i]) continue;
        dp[0][path_sz] += min(distX[i], distY[i]);
    }

    for(int i=0; i<n; i++){
        dp[i+1] = dp[i];
        if(!on_path[i]){
            ll d1 = min(distX[i], distY[i]), d2 = distX[i] + distY[i];
            for(int j=0; j<2*n; j++){
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + d1);
                if(j+2 < 2*n+1) dp[i+1][j+2] = min(dp[i+1][j+2], dp[i][j] + d2);
            }
        }
        else{
            ll d = abs(distX[i] - distY[i]);
            for(int j=0; j<2*n; j++){
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + d);
            }
        }
    }

    for(int i=0; i<=2*n+1; i++){
        if(dp[n][i] <= K) ans = max(ans, i);
    }
    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 106 ms 35652 KB Output is correct
2 Correct 118 ms 41040 KB Output is correct
3 Correct 46 ms 5500 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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