Submission #1242275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242275		a4n_	Closing Time (IOI23_closing)	C++20	0 / 100	1169 ms	1918592 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;
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    pq.push({0, x});
    pq.push({0, y});
    while(size(pq) > 0) {
        pll v = pq.top(); pq.pop();
        if(mark[v.S] == 1) continue;
        if(v.F > k) continue; 
        k -= v.F; 
        ans ++;
        mark[v.S] = 1;
        for(auto it : adj[v.S]) {
            if(mark[it.F] == 0) {
                pq.push({min(a[it.F], b[it.F]), it.F});
            }
        }
    }

    // for(int i=1; i<=n; i++) {
    //     if(a[i] > b[i]) swap(a[i], b[i]);
    // }

    // calc(x);

    // int mx = 0;
    // for(int i=x; i<=x; i++) {
    //     for(int j=1; j<=subt[i]*2; j++) {
    //         if(dp[i][j][2] <= k) mx = max(mx, j);
    //         if(dp[i][j][1] <= k) mx = max(mx, j);
    //         if(dp[i][j][0] <= k) mx = max(mx, j);
    //     }
    // }

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

    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