Submission #843406

#	Time	Username	Problem	Language	Result	Execution time	Memory
843406		Cookie	Closing Time (IOI23_closing)	C++17	83 / 100	908 ms	152352 KiB

closing

#include<bits/stdc++.h>
#include<fstream>
#include<closing.h>
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ll mxn = 2e5 + 5, inf = 1e18;
int n, x, y;
ll k;
int mxres = 0;
vt<pll>adj[mxn + 1];
vt<ll>compdep;
ll dp[3005][6005], distx[mxn + 1], disty[mxn + 1];
int u[mxn + 1], v[mxn + 1], w[mxn + 1];
bool path[mxn + 1];
int pa[3005];
void dfs(int s, int pre, ll dep, int root){
    if(root == x)distx[s] = dep;
    else disty[s] = dep;
    pa[s] = pre;
    for(auto [v, w]: adj[s]){
        if(v != pre){
            dfs(v, s, dep + w, root);
        }
    }
}
void ckmin(ll &a, ll b){
    a = min(a, b);
}
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; x = ++X; y = ++Y; k = K;
    for(int i = 1; i <= n; i++){
        adj[i].clear(); path[i] = 0;
    }
    bool ok = 1;
    for(int i = 0; i < n - 1; i++){
 
        u[i] = ++U[i]; v[i] = ++V[i]; w[i] = W[i];
        
        adj[u[i]].pb(make_pair(v[i], w[i])); adj[v[i]].pb(make_pair(u[i], w[i]));
    }
    dfs(x, -1, 0, x); dfs(y, -1, 0, y);
    vt<ll>comp;
    for(int i = 1; i <= n; i++)comp.pb(min(distx[i], disty[i]));
    sort(comp.begin(), comp.end());
    ll curr = 0;
    int ans = 0;
    for(int i = 0; i < sz(comp); i++){
        if(curr + comp[i] <= k){
            curr += comp[i]; ans++;
        }
    }
    if(n <= 3000){
    
    int node = x;
    do{
        path[node] = 1;
        
        node = pa[node];
    }while(node != y);
    path[y] = 1;
    for(int j = 0; j <= n; j++){
        for(int l = 0; l <= 2 * n; l++){
            dp[j][l] = inf;
        }
    }
    
    dp[0][0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= 2 * n; j++){
            if(dp[i][j] == inf)continue;
            if(path[i + 1]){
                ckmin(dp[i + 1][j + 1], dp[i][j] + min(distx[i + 1], disty[i + 1]));
                ckmin(dp[i + 1][j + 2], dp[i][j] + max(distx[i + 1], disty[i + 1]));
            }else{
                ckmin(dp[i + 1][j], dp[i][j]);
                ckmin(dp[i + 1][j + 1], dp[i][j] + min(distx[i + 1], disty[i + 1]));
                ckmin(dp[i + 1][j + 2], dp[i][j] + max(distx[i + 1], disty[i + 1]));
            }
        }
    }
    for(int i = 0; i <= 2 * n; i++){
        if(dp[n][i] <= k){
            ans = max(ans, i);
        }
    }
    
    }
    return(ans);
}
/*
int main()
{
 
    int Q;
    assert(1 == scanf("%d", &Q));
 
    std::vector<int> N(Q), X(Q), Y(Q);
    std::vector<long long> K(Q);
    std::vector<std::vector<int>> U(Q), V(Q), W(Q);
 
    for (int q = 0; q < Q; q++)
    {
        assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
 
        U[q].resize(N[q] - 1);
        V[q].resize(N[q] - 1);
        W[q].resize(N[q] - 1);
        for (int i = 0; i < N[q] - 1; ++i)
        {
            assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
        }
    }
    fclose(stdin);
 
    std::vector<int> result(Q);
    for (int q = 0; q < Q; q++)
    {
        result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
    }
 
    for (int q = 0; q < Q; q++)
    {
        printf("%d\n", result[q]);
    }
    fclose(stdout);
 
    return 0;
}
*/
/*
1
5 0 3 6
0 1 1
1 2 1
2 3 1
3 4 100
*/

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:50:10: warning: unused variable 'ok' [-Wunused-variable]
   50 |     bool ok = 1;
      |          ^~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 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