Submission #1242336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242336		a4n_	Closing Time (IOI23_closing)	C++20	0 / 100	1096 ms	31488 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
ll t, n, x, y, k, dp[3003][3003][3], pd[3003][3], a[N], b[N], subt[N];
vector<pll> adj[N];

void dfs(int v, int p=0, ll sum = 0) {
    a[v] = sum;
    for(auto u : adj[v]) {
        if(u.F == p) continue;
        dfs(u.F, v, u.S + sum);
    }
}
void dfs2(int v, int p=0, ll sum = 0) {
    b[v] = sum;
    for(auto u : adj[v]) {
        if(u.F == p) continue;
        dfs2(u.F, v, u.S + sum);
    }
}

void calc(int v, int p=0) {
    for(int i=1; i<=n*2; i++) {
        dp[v][i][0] = 1e18 + 1;
        dp[v][i][1] = 1e18 + 1;
        dp[v][i][2] = 1e18 + 1;
    }
    dp[v][0][1] = 1e18 + 1;
    dp[v][0][2] = 0;

    dp[v][1][0] = dp[v][1][2] = a[v];
    dp[v][2][1] = b[v];
    subt[v] = 1;

    if(size(adj[v]) == 1 && p > 0) {
        return;
    }

    for(auto u : adj[v]) {
        if(u.F == p) continue;
        calc(u.F, v);
        for(int i=0; i<=(subt[v] + subt[u.F])*2; i++) {
            pd[i][0] = pd[i][1] = pd[i][2] = 1e18 + 1;
        }
        
        for(int i=0; i<=subt[v]*2; i++) {
            for(int j=0; j<=subt[u.F]*2; j++) {
                pd[i + j][0] = min(dp[v][i][0] + dp[u.F][j][0], pd[i + j][0]);
                pd[i + j][1] = min(dp[v][i][1] + min(dp[u.F][j][0], dp[u.F][j][1]), pd[i + j][1]);
                pd[i + j][2] = min({dp[v][i][2] + dp[u.F][j][0], 
                    dp[v][i][0] + min(dp[u.F][j][2], dp[u.F][j][1]), pd[i+j][2]});
            }
        }
        
        subt[v] += subt[u.F];
        
        for(int i=0; i<=subt[v]*2; i++) {
            dp[v][i][0] = pd[i][0];
            dp[v][i][1] = pd[i][1];
            dp[v][i][2] = pd[i][2];
        }
    }
}

int mark[N];
int max_score(int _N, int _X, int _Y, long long _K, vector<int> U, vector<int> V, vector<int> W) {
    n = _N, k = _K, x = _X, y = _Y;
    x ++, y ++;

    for(int i=0; i<n-1; i++) {
        adj[V[i] + 1].pb({U[i] + 1, W[i]});
        adj[U[i] + 1].pb({V[i] + 1, W[i]});
    }

    dfs(x);
    dfs2(y);

    int ans = 0;
    if(x > y) {
        swap(x, y);
        for(int i=1; i<=n; i++) swap(a[i], b[i]);
    }
    for(int i=x; i<=n; i++) {
        for(int j=y; j>=1; j--) {
            ll tmp = k;
            int res = 0;
            vector<ll> vec;
            if(i < j) {
                for(int f=x; f<=i; f++) {
                    vec.pb(a[f]);
                }
                for(int f=j; f<=y; f++) {
                    vec.pb(b[f]);
                }
            } else {
                for(int f=j; f<=i; f++) {
                    tmp -= max(a[f], b[f]);
                }
                for(int f=x; f<j; f++) {
                    tmp -= a[f];
                }
                for(int f = i+1; f<=y; f++) {
                    tmp -= b[f];
                }
                res = (i - x + 1) + (y - j + 1);
            }
            if(tmp < 0) continue;
            for(int f=x-1; f>=1; f--) vec.pb(a[f]);
            for(int f=y+1; f<=n; f++) vec.pb(b[f]);
            sort(all(vec));
            reverse(all(vec));


            while(size(vec) > 0 && tmp >= vec.back()) {
                tmp -=vec.back();
                vec.pop_back();
                res ++;
            }
            ans = max(ans, res);
        }
    }

    for(int i=0; i<=n; i++) adj[i].clear(), mark[i] = 0;

    return ans;
}

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