제출 #1242259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242259		AlperenT_	봉쇄 시간 (IOI23_closing)	C++20	29 / 100	1094 ms	17220 KiB

closing

#include "closing.h"
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const ll maxn = 3000 + 10  ,s = 1000 , inf = 1e18 + 10 , mod = 998244353;
int par[maxn] , r[maxn]  , ma[maxn] , mark[maxn] , mb[maxn] ; ll dp[maxn][2*maxn]  ;
ll dis[maxn] , a[maxn] , b[maxn] ; 
vector <pii> G[maxn] ;
void dfs(int v){
    for(auto[u,w]  : G[v]){
        if(u == par[v])continue ;
        par[u] = v; 
        dfs(u) ;;
    }
}
void dist(int v, int p = -1){
    for(auto [u,w] : G[v]){
        if(u == p)continue ;
        dis[u ]= dis[v] + w ;
        dist(u , v); 
    }
}
void dfs2(int v, int p =-1 ){
    mark[v] =1 ;
    for(auto[u,w] : G[v]){
        if(mark[u] == 1)continue ;
        r[u] = r[v]; 
        dfs2(u ,v );  
    }
}

int max_score(int n, int x, int y, long long K,std::vector<int> U, std::vector<int> V, std::vector<int> W){
    rep(i , 0 ,n)G[i].clear() ;
    rep(i , 0 , n-2){
        G[V[i]].pb({U[i],W[i]}); 
        G[U[i]].pb({V[i] , W[i]}) ;
    }
    dis[x] =0 ;
    dist(x); 
    rep(i ,0, n-1){
        a[i] = dis[i] ;
    }
    dis[y] = 0;
    dist(y) ;
    rep(i ,0  ,n-1){
        b[i] = dis[i] ;
    }
    par[x] = -1 ;
    dfs(x) ;
    vector <int >vec ;
    int f = y ;
    while(f!=-1){
        vec.pb(f);
        f = par[f] ;
    }
    rep(i , 0 , n)mark[i] =0 ;
    for(int x : vec)mark[x] =1 ;
    for(int x : vec){
        r[x] = x ;
        dfs2(x) ;
    }
    reverse(all(vec)) ;
    int ans =0 ;
    rep(i , 0 ,n)ma[i] = mb[i] =0 ;
    rep(i , 0 ,sz(vec)-1){
        ma[vec[i]] = 1;
        per(j , sz(vec)-1 , 0){
            mb[vec[j]] =1 ;
            ll sm = K  ; int ted= 0 ;;
            vector<pair<ll,ll> > az; 
            bool ok =0 ; 
            rep(k , 0 ,n-1){
                if(r[k] == k){
                    ll mx = 0;
                    if(ma[k] == 1){ted++;mx =max(mx , a[k]);}
                    if(mb[k] == 1){ted++;mx =max(mx , b[k]);}
                    sm -= mx ; 
                }else{
                    if(ma[r[k]]+mb[r[k]] == 2){
                        az.pb({min(a[k],b[k]), max(a[k],b[k])}); 
                        ok =1 ;
                        continue ;
                    }
                    if(ma[r[k]]==1)az.pb({a[k] , -1});
                    if(mb[r[k]]==1)az.pb({b[k] , -1});
                }
            }
            if(sm < 0)continue ;
            // if(ok == 0){
            //     sort(all(az));
            //     rep(i , 0 ,sz(az)-1){
            //         if(sm < az[i].F)break ;
            //         sm -= az[i].F ;
            //         ted++ ;
            //     }
            //     ans = max(ans , ted) ;
            //     continue ;
            // }

            dp[0][0] = 0 ;
            rep(j ,1 ,2*n)dp[0][j] = inf; 
            rep(i , 1 , sz(az)){
                rep(j , 0, 2*n){
                    dp[i][j] = dp[i-1][j] ;
    
                    if(j){
                        dp[i][j] = min(dp[i][j] ,dp[i-1][j-1]+ az[i-1].F) ;
                    } 
                    if(j > 1 && az[i-1].S != -1){
                        dp[i][j] = min(dp[i][j] , dp[i-1][j-2] + az[i-1].S); 
                    }
                }
            }
            rep( j, 0 , 2*n){
                if(dp[sz(az)][j] <= sm){  
                    ans =max(ans ,ted + j) ;
                }
            }
        }
        rep(j  ,0 , sz(vec)-1)mb[vec[j]] =0 ;
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17