제출 #1223007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223007		nikd	봉쇄 시간 (IOI23_closing)	C++20	43 / 100	121 ms	38216 KiB

closing

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

int max_score(int n, int x, int y, long long k,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    
    vector<vector<array<ll, 2>>> adj(n);
    for(int i = 0; i<n-1; i++){
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i],W[i]});
    }
    int sol =0;

    //tre casi
    //primo caso: no intersezioni
    int sol1 = 0;
    vector<ll> dst(n, 1e18);
    function<void(int, int)> find_dst = [&](int v, int p){
        for(auto [u, w]: adj[v]){
            if(u==p) continue;
            dst[u] = min(dst[u], dst[v]+w);
            find_dst(u, v);
        }
        return;
    };
    dst[x] = 0;
    find_dst(x, -1);
    ll l = dst[y];
    dst[y] = 0;
    find_dst(y, -1);
    vector<ll> dst_ = dst;
    sort(dst_.begin(), dst_.end());
    ll k_ = k;
    for(ll i: dst_){
        if(k_-i >=0){
            k_-=i;
            sol1++;
        }
        else break;
    }
    sol = sol1;

    //secondo caso: intersezione solo nel path
    sol1 = 0;
    vector<ll> dst2;
    k_ = k;
    for(int i =0; i<x; i++) dst2.push_back(dst[i]);
    for(int i = y+1; i<n; i++) dst2.push_back(dst[i]);
    for(int i = x; i<=y; i++){
        k_-= dst[i];
        sol1++;
    }
    if(k_ < 0) return sol;
    for(int i = x; i<=y; i++){
        dst2.push_back(l-2*dst[i]);
        assert(l-2*dst[i] >= 0);
    }
    sort(dst2.begin(), dst2.end());
    for(ll i: dst2){
        if(k_ - i >= 0){
            k_ -= i;
            sol1++;
        }
        else break;
    }
    sol =max(sol, sol1);

    //terzo caso: le intersezioni strabordano
    sol1 = 0;
    k_ = k;
    for(int i = x; i<=y; i++){
        k_ -= max(dst[i], l-dst[i]);
        sol1 += 2;
    }
    if(k_ < 0) return sol;
    sol = max(sol1, sol);
    vector<int> dst3;
    for(int i=0; i<x; i++) dst3.push_back(dst[i]);
    for(int i=y+1; i<n; i++) dst3.push_back(dst[i]);
    sort(dst3.begin(), dst3.end());
    for(int i = 0; i<dst3.size(); i++){   
        k_ -= dst3[i];
        sol1++;
        if(k_<0) return sol; 
        ll k__ = k_;
        int sol1_ = sol1;
        for(int j = 0; j<=i; j++){
            if(k__-l>=0){
                k__-=l;
                sol1_++;
            }
            else break;
        }
        sol = max(sol, sol1_);
    }
    return sol;
}

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