제출 #1219279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219279		mariza	봉쇄 시간 (IOI23_closing)	C++20	9 / 100	1095 ms	5188 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=3000;
#define MID ((l+r)/2)

ll prefa[N], prefb[N], prefmax[N];
ll suma(ll l, ll r){
    if(r<l) return 0;
    else if(l==0) return prefa[r];
    else return prefa[r]-prefa[l-1];
}
ll sumb(ll l, ll r){
    if(r<l) return 0;
    else if(l==0) return prefb[r];
    else return prefb[r]-prefb[l-1];
}
ll summax(ll l, ll r){
    if(r<l) return 0;
    else if(l==0) return prefmax[r];
    else return prefmax[r]-prefmax[l-1];
}

vector<pair<ll,ll>> g[N];
ll idx[N];
void dfs(ll curr, ll prev){
    idx[curr]=idx[prev]+1;

    for(auto nxt:g[curr]){
        if(nxt.first!=prev) dfs(nxt.first,curr);
    }
}

ll dista[N], distb[N];
void dfsa(ll curr, ll prev, ll d){
    dista[idx[curr]]=d;

    for(auto nxt:g[curr]){
        if(nxt.first!=prev) dfsa(nxt.first,curr,d+nxt.second);
    }
}
void dfsb(ll curr, ll prev, ll d){
    distb[idx[curr]]=d;

    for(auto nxt:g[curr]){
        if(nxt.first!=prev) dfsb(nxt.first,curr,d+nxt.second);
    }
}

int max_score(int n, int a, int b, long long k, vector<int> u, vector<int> v, vector<int> w){
    for(ll i=0; i<n; i++){
        g[i].clear();
    }
    for(ll i=0; i<n-1; i++){
        g[u[i]].push_back({v[i],w[i]});
        g[v[i]].push_back({u[i],w[i]});
    }

    for(ll i=0; i<n; i++){
        if(g[i].size()==1){
            idx[i]=-1;
            dfs(i,i);
            break;
        }
    }

    if(idx[a]>idx[b]) swap(a,b);
    dfsa(a,a,0);
    dfsb(b,b,0);
    a=idx[a];
    b=idx[b];

    prefa[0]=dista[0];
    prefb[0]=distb[0];
    prefmax[0]=max(dista[0],distb[0]);
    for(ll i=1; i<n; i++){
        prefa[i]=prefa[i-1]+dista[i];
        prefb[i]=prefb[i-1]+distb[i];
        prefmax[i]=prefmax[i-1]+max(dista[i],distb[i]);
    }

    // vector<ll> x;
    // for(ll i=0; i<a; i++){
    //     x.push_back(dista[i]);
    // }
    // for(ll i=b+1; i<n; i++){
    //     x.push_back(distb[i]);
    // }
    // sort(x.begin(),x.end());
    // for(ll i=1; i<x.size(); i++){
    //     x[i]+=x[i-1];
    // }

    ll ans=0;
    for(ll ra=a; ra<n; ra++){
        for(ll lb=0; lb<=b; lb++){
            for(ll la=0; la<=a; la++){
                for(ll rb=b; rb<n; rb++){
                    if(suma(la,min(lb-1,ra))+sumb(max(lb,ra+1),rb)+summax(lb,ra)<=k){
                        // cout<<la<<" "<<ra<<" "<<lb<<" "<<rb<<" "<<max(ans,(ra-la+1)+(rb-lb+1))<<endl;
                        ans=max(ans,(ra-la+1)+(rb-lb+1));
                    }
                }
            }
            // ll s;
            // if(ra<lb) s=suma(a,ra)+sumb(lb,b);
            // else s=summax(lb,ra)+suma(a,lb-1)+sumb(ra+1,b);

            // if(s>k) continue;

            // ll l=0, r=x.size()-1, y=0;
            // while(l<=r){
            //     if(s+x[MID]<=k){
            //         y=MID+1;
            //         l=MID+1;
            //     }
            //     else r=MID-1;
            // }

            // cout<<"ra:"<<ra<<", lb:"<<lb<<" -> "<<y+(ra-a+1)+(b-lb+1)<<endl;
            // ans=max(ans,y+(ra-a+1)+(b-lb+1));
        }
    }

    return ans;
}

• 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