제출 #847478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847478		nvmdava	Closing Time (IOI23_closing)	C++17	8 / 100	159 ms	38596 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200'005;

vector<pair<int, ll> > adj[N];

ll dx[N];
int px[N];
int py[N];
ll dy[N];

ll d[N];
int p[N];


void dfs(int v, int par) {
    p[v] = par;
    for(auto& u : adj[v]) {
        if(u.first == par) continue;
        d[u.first] = u.second + d[v];
        dfs(u.first, 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)
{
    for(int i = 0; i < n; ++i){
        d[i] = dx[i] = dy[i] = p[i] = px[i] = py[i] = 0;
        adj[i].clear();
    }
    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]});
    }
    dfs(X, -1);
    swap(d, dx);
    swap(p, px);

    dfs(Y, -1);
    swap(d, dy);
    swap(p, py);

    int res = 0;

    vector<ll> dd;
    for(int i = 0; i < n; ++i) dd.push_back(min(dx[i], dy[i]));
    sort(dd.begin(), dd.end());
    ll tmp = k;
    for(int i = 0; i < n; ++i) {
        tmp -= dd[i];
        if(tmp >= 0) res = i + 1;
    }
    
    int cur = 0;
    dd.clear();
    for(int i = 0; i < n; ++i) {
        if(dx[i] + dy[i] == dx[Y]) {
            k -= min(dx[i], dy[i]);
            ++cur;
            if(k < 0) return res;
            dd.push_back(abs(dx[i] - dy[i]));
        }
    }

    sort(dd.begin(), dd.end());
    tmp = k;
    for(int i = 0; i < n; ++i) {
        tmp -= dd[i];
        if(tmp >= 0) res = i + 1 + cur;
    }

    return res;
}

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