Submission #960275

#	Time	Username	Problem	Language	Result	Execution time	Memory
960275		caterpillow	Closing Time (IOI23_closing)	C++17	35 / 100	1057 ms	69024 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; // treefix 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 x, int y, ll w = 1) { adj[x].pb({y, w}), adj[y].pb({x, w}); }
	void gen(int R = 0) { par[0][R] = R; dfs(R); }
	void dfs(int x = 0) {
		FOR (i, 1, par.size()) par[i][x] = par[i - 1][par[i - 1][x]];
		for (auto [y, w] : adj[x]) {
            if (y != par[0][x]) depth[y] = depth[par[0][y] = x] + 1, tfx[y] = tfx[x] + w, dfs(y);
        }
	}
	int jmp(int x, int d) {
		F0R (i, par.size()) if ((d >> i) & 1) x = par[i][x];
		return x; 
    }
	int lca(int x, int y) {
		if (depth[x] < depth[y]) swap(x, y);
		x = jmp(x, depth[x] - depth[y]); 
        if (x == y) return x;
		ROF (i, 0, par.size()) {
			int X = par[i][x], Y = par[i][y];
			if (X != Y) x = X, y = Y;
		}
		return par[0][x];
	}
	int dist(int x, int y) { // # edges on path
		return depth[x] + depth[y] - 2 * depth[lca(x, y)]; 
    }
    ll wdist(int x, int y) { // path sum
        return tfx[x] + tfx[y] - 2 * tfx[lca(x, y)];
    }
};

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:3: note: in expansion of macro 'FOR'
   41 |   FOR (i, 1, par.size()) par[i][x] = par[i - 1][par[i - 1][x]];
      |   ^~~
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:3: note: in expansion of macro 'F0R'
   47 |   F0R (i, par.size()) if ((d >> i) & 1) x = par[i][x];
      |   ^~~

• 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