Submission #1068659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068659		Arapak	Closing Time (IOI23_closing)	C++17	0 / 100	1091 ms	25680 KiB

closing

// Author: Kajetan Ramsza
#include "closing.h"
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;

#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto, auto> &p) {
    return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
    os<<"{";
    for(auto it=begin(v);it!=end(v);++it) {
        if(it!=begin(v)) os<<", ";
        os<<(*it);
    }
    return os<<"}";
}

void dbg_out(auto... x) {
    ((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

const ll inf = ll(1e18) + 7;

int n, x, y;
ll K;
vector<vector<pair<int, ll>>> g;
vll dist_x, dist_y;

int reachable(int v, int p, ll depth, const vll &closing) {
    int num = 1;
    for(auto [e, d] : g[v]) {
        if(e == p || closing[e] < depth + d) continue;
        num += reachable(e, v, depth+d, closing);
    }
    return num;
}

int calc(const vi &mask) {  
    vll closing(n, 0);
    rep(i,0,n) {
        if(mask[i] == 1) closing[i] = min(dist_x[i], dist_y[i]);
        else if(mask[i] == 2) closing[i] = max(dist_x[i], dist_y[i]);
    }
    ll sum = 0;
    rep(i,0,n) sum += closing[i];
    if(sum > K) return 0;
    int res = reachable(x,x,0,closing) + reachable(y,y,0,closing);
    dbg(mask, res);
    return res;
}

int solve() {
    int power = 1;
    rep(i,0,n)
        power *= 3;
    int result = 0;
    rep(mask,0,power) {
        vi m(n);
        int c_mask = mask;
        rep(i,0,n) {
            m[i] = c_mask % 3;
            c_mask /= 3;
        } 
        int res = calc(m);
        result = max(res, result);
    }
    return result;
}


vll distance(int root) {
    queue<int> q;
    q.push(root);
    vll dist(n, inf);
    dist[root] = 0;
    while(!q.empty()) {
        int v = q.front(); q.pop();
        for(auto [e, d] : g[v]) {
            if(dist[e] < inf) continue;
            dist[e] = dist[v] + d;
            q.push(e);
        }
    }
    return dist;
}


int max_score(int N, int X, int Y, ll _K,
             vi U, vi V, vi W) {
    n = N; x = X; y = Y; K = _K;
    dbg(n, x, y, K);
    g.resize(n);
    rep(i,0,n-1) {
        g[U[i]].emplace_back(V[i], W[i]);
        g[V[i]].emplace_back(U[i], W[i]);
    }
    dist_x = distance(x);
    dist_y = distance(y);
    int result = solve();
    g.clear();
    dist_x.clear();
    dist_y.clear();
    return result;
}

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