# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
841105 | 2023-09-01T09:09:34 Z | danikoynov | Closing Time (IOI23_closing) | C++17 | 48 ms | 10032 KB |
#include "closing.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3e3 + 10; vector < pair < int, ll > > adj[maxn]; ll dist[2][maxn]; int n; void bfs(int s, ll arr[]) { queue < int > q; for (int i = 0; i < n; i ++) arr[i] = -1; arr[s] = 0; q.push(s); while(!q.empty()) { int v = q.front(); q.pop(); for (pair < int, ll > nb : adj[v]) { if (arr[nb.first] == -1) { arr[nb.first] = arr[v] + nb.second; q.push(nb.first); } } } } const ll inf = 1e18; ll value[maxn]; ll dp[maxn][maxn], sub[maxn], temp[maxn]; void dfs(int v, int par) { sub[v] = 1; for (pair < int, ll > nb : adj[v]) { if (nb.first == par) continue; dfs(nb.first, v); } dp[v][0] = 0; dp[v][1] = max((ll)(0), dist[1][v] - value[v]); for (pair < int, ll > nb : adj[v]) { if (nb.first == par) continue; int u = nb.first; for (int i = 0; i <= sub[u] + sub[v]; i ++) temp[i] = inf; for (int i = 0; i <= sub[v]; i ++) for (int j = 0; j <= sub[u]; j ++) { if (i == 0 && j > 0) continue; temp[i + j] = min(temp[i + j], dp[v][i] + dp[u][j]); } for (int i = 0; i <= sub[v] + sub[u]; i ++) dp[v][i] = temp[i]; sub[v] += sub[u]; } } int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) { for (int i = 0; i < N; i ++) { dist[0][i] = dist[1][i] = 0; adj[i].clear(); value[i] = 0; } n = N; for (int i = 0; i < N - 1; i ++) { adj[U[i]].push_back({V[i], W[i]}); adj[V[i]].push_back({U[i], W[i]}); } bfs(X, dist[0]); bfs(Y, dist[1]); vector < pair < ll, int > > ord; ll left_k = K; for (int i = 0; i < N; i ++) { ord.push_back({dist[0][i], i}); } sort(ord.begin(), ord.end()); ///for (int i = 0; i < ord.size(); i ++) /// cout << "here " << ord[i].first << " " << ord[i].second << endl; ll ans = 0; for (int i = 0; i < ord.size(); i ++) { left_k = left_k - ord[i].first; if (left_k < 0) break; value[ord[i].second] = ord[i].first; dfs(Y, -1); /**cout << "step " << i + 1 << " " << left_k << endl; for (int j = 0; j <= N; j ++) cout << dp[Y][j] << " "; cout << endl;*/ ll cur = 0; int j = 0; while(j <= n && dp[Y][j] <= left_k) j ++; j --; cur = i + 1 + j; if (cur > ans) ans = cur; } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 48 ms | 10032 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 0 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 596 KB | Output is correct |
7 | Correct | 0 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 0 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 596 KB | Output is correct |
11 | Correct | 1 ms | 596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 0 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 596 KB | Output is correct |
7 | Correct | 0 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 0 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 596 KB | Output is correct |
11 | Correct | 1 ms | 596 KB | Output is correct |
12 | Correct | 2 ms | 724 KB | Output is correct |
13 | Correct | 1 ms | 724 KB | Output is correct |
14 | Correct | 2 ms | 724 KB | Output is correct |
15 | Correct | 1 ms | 724 KB | Output is correct |
16 | Correct | 2 ms | 796 KB | Output is correct |
17 | Correct | 2 ms | 852 KB | Output is correct |
18 | Incorrect | 1 ms | 468 KB | 2nd lines differ - on the 1st token, expected: '25', found: '24' |
19 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 0 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 1 ms | 596 KB | Output is correct |
7 | Correct | 0 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 0 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 596 KB | Output is correct |
11 | Correct | 1 ms | 596 KB | Output is correct |
12 | Correct | 2 ms | 724 KB | Output is correct |
13 | Correct | 1 ms | 724 KB | Output is correct |
14 | Correct | 2 ms | 724 KB | Output is correct |
15 | Correct | 1 ms | 724 KB | Output is correct |
16 | Correct | 2 ms | 796 KB | Output is correct |
17 | Correct | 2 ms | 852 KB | Output is correct |
18 | Incorrect | 1 ms | 468 KB | 2nd lines differ - on the 1st token, expected: '25', found: '24' |
19 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 0 ms | 468 KB | Output is correct |
7 | Incorrect | 0 ms | 340 KB | 1st lines differ - on the 1st token, expected: '6', found: '5' |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 0 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 596 KB | Output is correct |
8 | Correct | 0 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 0 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 596 KB | Output is correct |
12 | Correct | 1 ms | 596 KB | Output is correct |
13 | Correct | 2 ms | 724 KB | Output is correct |
14 | Correct | 1 ms | 724 KB | Output is correct |
15 | Correct | 2 ms | 724 KB | Output is correct |
16 | Correct | 1 ms | 724 KB | Output is correct |
17 | Correct | 2 ms | 796 KB | Output is correct |
18 | Correct | 2 ms | 852 KB | Output is correct |
19 | Incorrect | 0 ms | 340 KB | 1st lines differ - on the 1st token, expected: '6', found: '5' |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 0 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 596 KB | Output is correct |
8 | Correct | 0 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 0 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 596 KB | Output is correct |
12 | Correct | 1 ms | 596 KB | Output is correct |
13 | Correct | 2 ms | 724 KB | Output is correct |
14 | Correct | 1 ms | 724 KB | Output is correct |
15 | Correct | 2 ms | 724 KB | Output is correct |
16 | Correct | 1 ms | 724 KB | Output is correct |
17 | Correct | 2 ms | 796 KB | Output is correct |
18 | Correct | 2 ms | 852 KB | Output is correct |
19 | Incorrect | 1 ms | 468 KB | 2nd lines differ - on the 1st token, expected: '25', found: '24' |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 0 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 596 KB | Output is correct |
8 | Correct | 0 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 0 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 596 KB | Output is correct |
12 | Correct | 1 ms | 596 KB | Output is correct |
13 | Correct | 2 ms | 724 KB | Output is correct |
14 | Correct | 1 ms | 724 KB | Output is correct |
15 | Correct | 2 ms | 724 KB | Output is correct |
16 | Correct | 1 ms | 724 KB | Output is correct |
17 | Correct | 2 ms | 796 KB | Output is correct |
18 | Correct | 2 ms | 852 KB | Output is correct |
19 | Incorrect | 1 ms | 468 KB | 2nd lines differ - on the 1st token, expected: '25', found: '24' |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 468 KB | Output is correct |
4 | Correct | 0 ms | 468 KB | Output is correct |
5 | Correct | 0 ms | 468 KB | Output is correct |
6 | Correct | 0 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 596 KB | Output is correct |
8 | Correct | 0 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 0 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 596 KB | Output is correct |
12 | Correct | 1 ms | 596 KB | Output is correct |
13 | Correct | 2 ms | 724 KB | Output is correct |
14 | Correct | 1 ms | 724 KB | Output is correct |
15 | Correct | 2 ms | 724 KB | Output is correct |
16 | Correct | 1 ms | 724 KB | Output is correct |
17 | Correct | 2 ms | 796 KB | Output is correct |
18 | Correct | 2 ms | 852 KB | Output is correct |
19 | Incorrect | 1 ms | 468 KB | 2nd lines differ - on the 1st token, expected: '25', found: '24' |
20 | Halted | 0 ms | 0 KB | - |