oj.uz

Submission #1068659

# Submission time Handle Problem Language Result Execution time Memory
1068659 2024-08-21T11:14:21 Z Arapak Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 25680 KB 
// 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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 25680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1091 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1091 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1091 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1091 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1091 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1091 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1091 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1091 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -