oj.uz

Submission #960270

# Submission time Handle Problem Language Result Execution time Memory
960270 2024-04-10T06:17:17 Z caterpillow Closing Time (IOI23_closing) C++17
35 / 100
 1000 ms 69084 KB 
#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

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 / 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 1057 ms 69084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 2 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 2 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 3 ms 348 KB Output is correct
26 Correct 70 ms 1424 KB Output is correct
27 Correct 2 ms 1372 KB Output is correct
28 Correct 58 ms 1372 KB Output is correct
29 Correct 58 ms 1372 KB Output is correct
30 Correct 2 ms 1116 KB Output is correct
31 Correct 38 ms 1372 KB Output is correct
32 Correct 37 ms 1372 KB Output is correct

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 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
8 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 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
20 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 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 2 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
27 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 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 2 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 3 ms 348 KB Output is correct
27 Correct 70 ms 1424 KB Output is correct
28 Correct 2 ms 1372 KB Output is correct
29 Correct 58 ms 1372 KB Output is correct
30 Correct 58 ms 1372 KB Output is correct
31 Correct 2 ms 1116 KB Output is correct
32 Correct 38 ms 1372 KB Output is correct
33 Correct 37 ms 1372 KB Output is correct
34 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 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 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 2 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 2 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 3 ms 348 KB Output is correct
27 Correct 70 ms 1424 KB Output is correct
28 Correct 2 ms 1372 KB Output is correct
29 Correct 58 ms 1372 KB Output is correct
30 Correct 58 ms 1372 KB Output is correct
31 Correct 2 ms 1116 KB Output is correct
32 Correct 38 ms 1372 KB Output is correct
33 Correct 37 ms 1372 KB Output is correct
34 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
35 Halted 0 ms 0 KB -