Submission #1209815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209815		PagodePaiva	Closing Time (IOI23_closing)	C++20	75 / 100	520 ms	147200 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>

using namespace std;
const long long N = 3010;

long long dp[N][2*N];
vector <pair <long long, long long>> g[N];
long long mark[N];
long long custox[N], custoy[N];
long long l[N], r[N];
int pai[N];
int esp[N];

void dfs_x(int v, int p){
    pai[v] = p;
    for(auto [x, w] : g[v]){
        if(x == p)
            continue;
        custox[x] = custox[v] + w;
        dfs_x(x, v);
    }
    return;
}

void dfs_y(int v, int p){
    for(auto [x, w] : g[v]){
        if(x == p)
            continue;
        custoy[x] = custoy[v] + w;
        dfs_y(x, v);
    }
    return;
}

int max_score(int n, int X, int Y, long long k,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
    for(int i = 0;i < n;i++){
        g[i].clear();
        mark[i] = 0;
        custox[i] = custoy[i] = 0;
        for(int j = 0;j < 2*n+2;j++)
            dp[i][j] = 0;
        l[i] = r[i] = 0;
        pai[i] = 0;
        esp[i] = 0;
    }
    for(long long i = 0;i < n-1;i++){
        g[U[i]].push_back({V[i], W[i]});
        g[V[i]].push_back({U[i], W[i]});
    }
    priority_queue <pair <long long, long long>> pq;
    pq.push({0, X});
    pq.push({0, Y});
    long long ans = 0, sum = 0;
    while(!pq.empty()){
        auto [w, v] = pq.top();
        pq.pop();
        if(mark[v])
            continue;
        w *= -1;
        if(sum+w > k){
            break;
        }
        sum += w;
        ans++;
        mark[v] = 1;
        for(auto [x, ww] : g[v]){
            if(mark[x])
                continue;
            pq.push({-(ww+w), x});
        }
    }
    dfs_x(X, X);
    dfs_y(Y, Y);
    for(int i = 0;i < n;i++){
        l[i] = min(custox[i], custoy[i]);
        r[i] = max(custox[i], custoy[i]) - l[i];
    }
    long long calc = 0;
    int pref = 0;
    while(Y != X){
        esp[Y] = 1;
        calc += l[Y];
        Y = pai[Y];
        pref++;
    }
    esp[X] = 1;
    pref++;
    if(calc > k)
        return ans;
    //cout << pref << ' ' << calc << '\n';
    k -= calc;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < 2*n+2;j++){
            dp[i][j] = 1e18+10;
        }
    }
    dp[0][0] = 0;
    if(esp[0] == 0){
        dp[0][1] = l[0];
        dp[0][2] = l[0] + r[0];
    }
    else{
        dp[0][1] = r[0];
    }
    for(int i = 1;i < n;i++){
        for(int j = 0;j < 2*n+2;j++){
            if(esp[i] == 0){
                dp[i][j] = min(min(dp[i][j], dp[i-1][j]), min((j > 0 ? dp[i-1][j-1] + l[i] : (long long)(1e18+10)), (j > 1 ? dp[i-1][j-2] + l[i] + r[i] : (long long)(1e18+10))));
            }
            else{
                dp[i][j] = min({dp[i][j], dp[i-1][j], (j > 0 ? dp[i-1][j-1] + r[i] : (long long)(1e18+10))});
            }
        }
    }
    for(int i = 0;i < 2*n+2;i++){
        //cout << dp[n-1][i] << ' '; 
    }
    for(int i = 2*n+1;i >= 0;i--){
        if(dp[n-1][i] <= k){
            return max((long long)(i+pref), ans);
        }
    }
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:125:1: warning: control reaches end of non-void function [-Wreturn-type]
  125 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 17