oj.uz

Submission #1068557

# Submission time Handle Problem Language Result Execution time Memory
1068557 2024-08-21T10:36:52 Z Arapak Closing Time (IOI23_closing) C++17
8 / 100
 86 ms 30260 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;

vi stk;
bool dfs_find(int v, int p, int dest) {
    stk.push_back(v);
    if(v == dest) return true;
    for(auto [e, d] : g[v]) {
        if(e == p) continue;
        if(dfs_find(e, v, dest)) return true;
    }
    stk.pop_back();
    return false;
}

int solve(int root = -1) {
    using T = tuple<ll, int, int>;
    priority_queue<T, vector<T>, greater<T>> q;
    vector<ll> closing(n, 0);
    
    ll k = K;
    int res = 2;
    if(root != -1) {
        dfs_find(x, x, root);
        for(auto v : stk) {
            if(v == x) continue;
            k -= max(0ll, dist_x[v] - closing[v]);
            closing[v] = max(closing[v], dist_x[v]);
            res++;
        }
        stk.clear();

        dfs_find(y, y, root);
        for(auto v : stk) {
            if(v == y) continue;
            k -= max(0ll, dist_y[v] - closing[v]);
            closing[v] = max(closing[v], dist_y[v]);
            res++;
        }
        stk.clear();
        dbg(k, res);
        if(k < 0) return 0;
    }

    auto visited = [&](int v, int root) -> bool {
        return closing[v] >= (root == x ? dist_x[v] : dist_y[v]);
    };
    auto add_new = [&](int v, int root) {
        if(!visited(v, root)) return;
        dbg(v, root);
        for(auto [e, d] : g[v]) {
            if(visited(e, root)) continue;
            q.push({(root == x ? dist_x[e] : dist_y[e]) - closing[e], e, root});
        }
    };

    rep(v,0,n) {
        add_new(v, x);
        add_new(v, y);
    }

    while(!q.empty()) {
        auto [cost, v, root] = q.top(); q.pop();
        if(visited(v, root)) continue;
        dbg(cost, v, root);
        if(cost > k) return res;
        k -= cost;
        closing[v] = root == x ? dist_x[v] : dist_y[v];
        res++;
        add_new(v, root);
    }
    return res;
}

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;
}

vi find_least_diff() {
    dist_x = distance(x);
    dist_y = distance(y);
    auto cmp = [&](int v) {
        return make_pair((ll)abs(dist_x[v] - dist_y[v]), min(dist_x[v], dist_y[v]));
    };

    vi mini = {0};
    rep(i,1,n) {
        if(cmp(i) < cmp(mini[0]))
            mini = {i};
        else if(cmp(i) == cmp(mini[0]))
            mini.push_back(i);
    }
    return mini;
}

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]);
    }
    vi least_diff = find_least_diff();
    dbg(least_diff);
    int result = solve();
    dbg(result);
    for(auto v : least_diff) {
        int res = solve(v);
        dbg(v, res);
        result = max(result, res);
    }
    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 348 KB Output is correct

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 27452 KB Output is correct
2 Correct 86 ms 30260 KB Output is correct
3 Correct 48 ms 2900 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '30', found: '27'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '30', found: '27'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '30', found: '27'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '30', found: '27'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '30', found: '27'
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '30', found: '27'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '30', found: '27'
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '30', found: '27'
4 Halted 0 ms 0 KB -