Submission #960270

#	Time	Username	Problem	Language	Result	Execution time	Memory
960270		caterpillow	Closing Time (IOI23_closing)	C++17	35 / 100	1057 ms	69084 KiB

closing

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end() 
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e18;

int n, x, y;
ll k;
vt<vt<pl>> adj;
vt<ll> ct;
 
struct LCA {
    int n; 
    vt<vt<pl>> adj; 
    vt<vt<int>> par;
    vt<int> depth;
    vt<ll> tfx; // treefiu sum
    void init(int _n) {  n = _n;
        int d = 1; 
        while ((1<<d) < n) ++d;
        par.assign(d, vt<int>(n)); 
        adj.resize(n);
        depth.resize(n);
        tfx.resize(n);
    }
    void ae(int u, int v, ll w = 1) { adj[u].pb({v, w}), adj[v].pb({u, w}); }
    void gen(int R = 0) { par[0][R] = R; dfs(R); }
    void dfs(int u = 0) {
        FOR (i, 1, par.size()) par[i][u] = par[i - 1][par[i - 1][u]];
        for (auto [v, w] : adj[u]) {
            if (v != par[0][u]) depth[v] = depth[par[0][v] = u] + 1, tfx[v] = tfx[u] + w, dfs(v);
        }
    }
    int jmp(int u, int d) {
        F0R (i, par.size()) if ((d >> i) & 1) u = par[i][u];
        return u; 
    }
    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        u = jmp(u, depth[u] - depth[v]); 
        if (u == v) return u;
        ROF (i, 0, par.size()) {
            int U = par[i][u];
            int V = par[i][v];
            if (U != V) u = U, v = V;
        }
        return par[0][u];
    }
    int dist(int u, int v) { // # edges on path
        return depth[u] + depth[v] - 2 * depth[lca(u, v)]; 
    }
    // onlv if weighted paths
    ll wdist(int u, int v) { // path sum
        return tfx[u] + tfx[v] - 2 * tfx[lca(u, v)];
    }
};

int max_score(int N, int X, int Y, ll K, vt<int> U, vt<int> V, vt<int> W) {
    n = N, x = X, y = Y;
    k = K;
    adj.assign(n, {});
    ct.assign(n, 0);
    LCA lca;
    lca.init(n);
    F0R (i, n - 1) {
        int u = U[i], v = V[i], w = W[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
        lca.ae(u, v, w);
    }
    lca.gen();

    ll used = 0;
    int ans = 2;
    vt<vt<bool>> reached(n, {0, 0});
    reached[x][0] = reached[y][1] = true;
    using t3 = tuple<ll, int, int>;
    while (true) {
        t3 best = {INF, -1, -1};
        F0R (i, n) {
            if (!reached[i][0]) {
                bool good = false;
                for (auto [v, w] : adj[i]) {
                    if (reached[v][0]) good = true;
                }
                if (good) best = min(best, {lca.wdist(i, x) - ct[i], i, 0});
            }
            if (!reached[i][1]) {
                bool good = false;
                for (auto [v, w] : adj[i]) {
                    if (reached[v][1]) good = true;
                }
                if (good) best = min(best, {lca.wdist(i, y) - ct[i], i, 1});
            }
        }
        auto [cost, u, orig] = best;
        if (used + cost > k) break;
        used += max(0ll, cost);
        ans++;
        reached[u][orig] = true;
        ct[u] += max(0ll, cost);
    }
    return ans;
}

Compilation message (stderr)

closing.cpp: In member function 'void LCA::dfs(int)':
closing.cpp:12:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
closing.cpp:41:9: note: in expansion of macro 'FOR'
   41 |         FOR (i, 1, par.size()) par[i][u] = par[i - 1][par[i - 1][u]];
      |         ^~~
closing.cpp: In member function 'int LCA::jmp(int, int)':
closing.cpp:12:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
closing.cpp:14:19: note: in expansion of macro 'FOR'
   14 | #define F0R(i, b) FOR (i, 0, b)
      |                   ^~~
closing.cpp:47:9: note: in expansion of macro 'F0R'
   47 |         F0R (i, par.size()) if ((d >> i) & 1) u = par[i][u];
      |         ^~~

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