oj.uz

Submission #960278

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

    ll time = chrono::steady_clock::now().time_since_epoch().count();
    if (ans == 5) ans++;
    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: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];
      |   ^~~
closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:114:8: warning: unused variable 'time' [-Wunused-variable]
  114 |     ll time = chrono::steady_clock::now().time_since_epoch().count();
      |        ^~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 69188 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 1 ms 760 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 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 1 ms 760 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 600 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 1 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 1 ms 760 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 600 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 1 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 4 ms 348 KB Output is correct
26 Correct 60 ms 1372 KB Output is correct
27 Correct 2 ms 1372 KB Output is correct
28 Correct 57 ms 1372 KB Output is correct
29 Correct 64 ms 1372 KB Output is correct
30 Correct 2 ms 1112 KB Output is correct
31 Correct 37 ms 1372 KB Output is correct
32 Correct 41 ms 1368 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '5', found: '6'
9 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 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 760 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 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '5', found: '6'
21 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 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 760 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 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 600 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 1 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '5', found: '6'
28 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 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 760 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 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 600 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 1 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 4 ms 348 KB Output is correct
27 Correct 60 ms 1372 KB Output is correct
28 Correct 2 ms 1372 KB Output is correct
29 Correct 57 ms 1372 KB Output is correct
30 Correct 64 ms 1372 KB Output is correct
31 Correct 2 ms 1112 KB Output is correct
32 Correct 37 ms 1372 KB Output is correct
33 Correct 41 ms 1368 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '5', found: '6'
36 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 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 760 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 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 600 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 1 ms 348 KB Output is correct
25 Correct 2 ms 348 KB Output is correct
26 Correct 4 ms 348 KB Output is correct
27 Correct 60 ms 1372 KB Output is correct
28 Correct 2 ms 1372 KB Output is correct
29 Correct 57 ms 1372 KB Output is correct
30 Correct 64 ms 1372 KB Output is correct
31 Correct 2 ms 1112 KB Output is correct
32 Correct 37 ms 1372 KB Output is correct
33 Correct 41 ms 1368 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '5', found: '6'
36 Halted 0 ms 0 KB -