Submission #1082430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082430		idas	Closing Time (IOI23_closing)	C++17	75 / 100	508 ms	142424 KiB

closing

#include "bits/stdc++.h"
#include "closing.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)(x).size())
#define pb push_back
#define s second
#define f first

using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;

const int N=3e3+10;
ll k, d[N][2], dp[2*N][N], mn[N], mx[N];
vector<pii> ad[N];
int n, x, y;

void build(int u, int in, int pst=-1) {
    for(auto [nxt, w] : ad[u]) {
        if(nxt==pst) continue;
        d[nxt][in]=d[u][in]+w;
        build(nxt, in, u);
    }
}

vi path, now;
void get_path(int u, int pst=-1) {
    now.pb(u);
    if(u==y) {
        path=now;
        return;
    }
    for(auto [it, w] : ad[u]) {
        if(it==pst) continue;
        get_path(it, u);
    }
    now.pop_back();
}

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    path.clear(); now.clear();
    n=N; x=X; y=Y; k=K;
    FOR(i, 0, n) ad[i].clear();
    FOR(i, 0, n-1) {
        ad[U[i]].pb({V[i],W[i]});
        ad[V[i]].pb({U[i],W[i]});
    }

    d[x][0]=d[y][1]=0;
    build(x, 0);
    build(y, 1);
    get_path(x);

    FOR(i, 0, n) mn[i+1]=min(d[i][0], d[i][1]), mx[i+1]=max(d[i][0], d[i][1]);

    vector<ll> inf;
    FOR(i, 1, n+1) inf.pb(mn[i]);
    sort(inf.begin(), inf.end());
    ll now_sum=0; int ans=0;
    for(auto it : inf) {
        if(now_sum+it>k) break;
        now_sum+=it;
        ans++;
    }

    now_sum=0;
    vector dif(n+1, false);
    for(auto it : path) {
        dif[it+1]=true;
        now_sum+=mn[it+1];
    }

    FOR(i, 0, 2*n+1) FOR(j, 0, n+1) dp[i][j]=1e18;
    FOR(j, 0, n+1) dp[sz(path)][j]=now_sum;

    FOR(i, 1, 2*n+1) {
        FOR(j, 1, n+1) {
            if(dif[j]) {
                if(i>=1) dp[i][j]=min(dp[i][j], dp[i-1][j-1]+mx[j]-mn[j]);
            }
            else {
                if(i>=1) dp[i][j]=min(dp[i][j], dp[i-1][j-1]+mn[j]);
                if(i>=2) dp[i][j]=min(dp[i][j], dp[i-2][j-1]+mx[j]);
            }
            dp[i][j]=min(dp[i][j], dp[i][j-1]);
        }
    }

    for(int i=2*n; i>=0; i--) {
        if(dp[i][n]<=k) ans=max(ans, i);
    }
    return ans;
}
/*
1
5 0 3 11
0 1 5
1 2 1
2 3 6
3 4 5

1
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3

1
4 0 3 20
0 1 18
1 2 1
2 3 19

1
8 1 3 14
0 1 3
1 2 2
2 3 1
3 4 5
4 5 2
5 6 3
6 7 1
*/

• 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