제출 #1194564

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194564		edga1	봉쇄 시간 (IOI23_closing)	C++20	9 / 100	1097 ms	23364 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<ll> ax(N,0),ay(N,0),l1(N),l2(N);
    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});
            }
        }
    }
    l1[0]=min(ax[0],ay[0]);
    l2[0]=max(ax[0],ay[0])-l1[0];
    for(int i=1; i<N; i++){
        l1[i]=min(ax[i],ay[i])+l1[i-1];
        l2[i]=max(ax[i],ay[i])-min(ax[i],ay[i])+l2[i-1];
    }
    int rez=0;
    for(int l=0; l<=X; l++){
        for(int r=Y; r<N; r++){
            ll sum=l1[r];
            if(l!=0) sum-=l1[l-1];
            if(sum<=k){
                int m=0,a=l+1,b=l;
                while(b<=r){
                    ll c=l2[b]-l2[a-1];
                    if(sum+c<=k){
                        m=max(m,b-a+1);
                        b++;
                    }else{
                        a++;
                    }
                }
                rez=max(rez,r-l+1+m);
            }else{
                int m=1e9,a=X+1,b=X+1;
                while(b<r){
                    ll c=l1[b]-l1[a-1];
                    if(sum-c<=k){
                        m=min(m,b-a+1);
                        a++;
                    }else{
                        b++;
                    }
                }
                rez=max(rez,r-l+1-m);
            }
        }
    }
    return rez;
}
/*
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