Submission #1194441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194441		edga1	Closing Time (IOI23_closing)	C++20	9 / 100	1093 ms	19524 KiB

closing

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define fi first
#define se second
#define pb push_back
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MOD 1000000007

int max_score(int N, int X, int Y, ll k, vector<int> U, vector<int> V, vector<int> W){
    if(X>Y) swap(X,Y);
    vector<pair<int,int>> c[N];
    for(int i=0; i<N-1; i++){
        c[U[i]].pb({V[i],W[i]});
        c[V[i]].pb({U[i],W[i]});
    }
    vector<int> ax(N,0),ay(N,0),m(N,0);
    stack<pair<int,int>> s;
    s.push({X,0});
    while(!s.empty()){
        pair<int,int> cur=s.top();
        s.pop();
        for(int i=0; i<c[cur.fi].size(); i++){
            if(ax[c[cur.fi][i].fi]==0 && c[cur.fi][i].fi!=X){
                ax[c[cur.fi][i].fi]=cur.se+c[cur.fi][i].se;
                s.push({c[cur.fi][i].fi,cur.se+c[cur.fi][i].se});
            }
        }
    }
    s.push({Y,0});
    while(!s.empty()){
        pair<int,int> cur=s.top();
        s.pop();
        for(int i=0; i<c[cur.fi].size(); i++){
            if(ay[c[cur.fi][i].fi]==0 && c[cur.fi][i].fi!=Y){
                ay[c[cur.fi][i].fi]=cur.se+c[cur.fi][i].se;
                s.push({c[cur.fi][i].fi,cur.se+c[cur.fi][i].se});
            }
        }
    }
    m[0]=max(ax[0],ay[0]);
    for(int i=1; i<N; i++){
        m[i]=m[i-1]+max(ax[i],ay[i]);
        ax[i]+=ax[i-1];
        ay[i]+=ay[i-1];
    }
    int r=0;
    for(int sx=0; sx<=X; sx++){
        for(int bx=X; bx<N; bx++){
            for(int sy=sx; sy<=Y; sy++){
                for(int by=max(Y,bx); by<N; by++){
                    ll sum=ax[min(bx,sy-1)]+ay[by]-ay[max(sy-1,bx)];
                    if(sx>0) sum-=ax[sx-1];
                    if(bx>=sy) sum+=m[bx]-m[sy-1];
                    if(sum<=k){
                        r=max(r,bx+by-sx-sy+2);
                    }
                }
            }
        }
    }
    return r;
}
/*
int main()
{
    fastIO;
    int t=1;
    cin>>t;
    while(t--){
        int n,x,y;
        ll k;
        cin>>n>>x>>y>>k;
        vector<int> U(n), V(n), W(n);
        for(int i=0; i<n-1; i++){
            cin>>U[i]>>V[i]>>W[i];
        }
        cout<<max_score(n,x,y,k,U,V,W)<<'\n';
    }
    return 0;
}*/

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