oj.uz

Submission #1072276

# Submission time Handle Problem Language Result Execution time Memory
1072276 2024-08-23T16:16:21 Z sammyuri Closing Time (IOI23_closing) C++17
43 / 100
 953 ms 146888 KB 
#include "closing.h"

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;
typedef long long ll;
const ll INF = 4e18;

int n;
int x, y; ll k;
ll dp[MAXN][2 * MAXN];
ll mindist[MAXN], maxdist[MAXN];
vector<int> curpath;
bool forced[MAXN];
vector<pair<int, ll>> adj[200005];
priority_queue<ll> pq;

void dfs1(int node, int parent, ll curdist) {
    pq.push(-curdist);
    for (auto a : adj[node])
        if (a.first != parent)
            dfs1(a.first, node, a.second + curdist);
}
void dfs2(int node, int parent, ll curdist) {
    mindist[node] = min(mindist[node], curdist);
    maxdist[node] = max(maxdist[node], curdist);
    for (auto a : adj[node])
        if (a.first != parent)
            dfs2(a.first, node, a.second + curdist);
}
bool dfs3(int node, int parent) {
    curpath.push_back(node);
    if (node == y) {
        for (auto a : curpath)
            forced[a] = true;
        return true;
    }
    for (auto a : adj[node])
        if (a.first != parent)
            if (dfs3(a.first, node))
                return true;
    curpath.pop_back();
    return false;
}

int solve_brute() {
    while (pq.size())
        pq.pop();
    dfs1(x, -1, 0); dfs1(y, -1, 0);
    int ans = 0;
    ll cost = 0;
    while (cost <= k && pq.size()) {
        ll cur = -pq.top(); pq.pop();
        if (cost + cur <= k)
            ans ++, cost += cur;
        else break;
    }
    return ans;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    memset(forced, false, sizeof(forced));
    n = N;
    x = X; y = Y; k = K;
    for (int i = 0; i < n - 1; i ++) {
        int a, b; ll c;
        a = U[i]; b = V[i]; c = W[i];
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    if (N > MAXN) {
        int ans = solve_brute();
        for (int i = 0; i < n; i ++)
            adj[i].clear();
        return ans;
    }
    for (int i = 0; i <= N; i ++)
        for (int j = 0; j <= 2 * N; j ++)
            dp[i][j] = INF;
    for (int i = 0; i < n; i ++)
        maxdist[i] = 0, mindist[i] = INF;
    curpath.clear();
    dfs2(x, -1, 0); dfs2(y, -1, 0);
    dfs3(x, -1);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i ++) {
        // do not take
        if (!forced[i])
            for (int j = 0; j <= 2 * n; j ++)
                dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        // take once
        for (int j = 1; j <= 2 * n; j ++) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + mindist[i - 1]);
        }
        // take twice
        for (int j = 2; j <= 2 * n; j ++) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 2] + maxdist[i - 1]);
        }
    }
    int best = 0;
    for (int j = 0; j <= 2 * n; j ++)
        if (dp[n][j] <= k)
            best = max(best, j);
    best = max(best, solve_brute());
        for (int i = 0; i < n; i ++)
            adj[i].clear();
    return best;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 32136 KB Output is correct
2 Correct 84 ms 37312 KB Output is correct
3 Correct 953 ms 30012 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 3 ms 5316 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 4 ms 5720 KB Output is correct
13 Correct 3 ms 5720 KB Output is correct
14 Correct 3 ms 5468 KB Output is correct
15 Correct 3 ms 5468 KB Output is correct
16 Correct 3 ms 5724 KB Output is correct
17 Correct 2 ms 5724 KB Output is correct
18 Correct 2 ms 5212 KB Output is correct
19 Correct 7 ms 11100 KB Output is correct
20 Correct 6 ms 10332 KB Output is correct
21 Correct 6 ms 10588 KB Output is correct
22 Correct 5 ms 11100 KB Output is correct
23 Correct 5 ms 11100 KB Output is correct
24 Correct 5 ms 11100 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 3 ms 5316 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 4 ms 5720 KB Output is correct
13 Correct 3 ms 5720 KB Output is correct
14 Correct 3 ms 5468 KB Output is correct
15 Correct 3 ms 5468 KB Output is correct
16 Correct 3 ms 5724 KB Output is correct
17 Correct 2 ms 5724 KB Output is correct
18 Correct 2 ms 5212 KB Output is correct
19 Correct 7 ms 11100 KB Output is correct
20 Correct 6 ms 10332 KB Output is correct
21 Correct 6 ms 10588 KB Output is correct
22 Correct 5 ms 11100 KB Output is correct
23 Correct 5 ms 11100 KB Output is correct
24 Correct 5 ms 11100 KB Output is correct
25 Correct 5 ms 5464 KB Output is correct
26 Correct 125 ms 146888 KB Output is correct
27 Correct 109 ms 136788 KB Output is correct
28 Correct 78 ms 137808 KB Output is correct
29 Correct 87 ms 142928 KB Output is correct
30 Correct 88 ms 136028 KB Output is correct
31 Correct 89 ms 146768 KB Output is correct
32 Correct 83 ms 146828 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Incorrect 2 ms 5212 KB 1st lines differ - on the 1st token, expected: '14', found: '12'
11 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5316 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 4 ms 5720 KB Output is correct
14 Correct 3 ms 5720 KB Output is correct
15 Correct 3 ms 5468 KB Output is correct
16 Correct 3 ms 5468 KB Output is correct
17 Correct 3 ms 5724 KB Output is correct
18 Correct 2 ms 5724 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 4952 KB Output is correct
21 Correct 2 ms 4956 KB Output is correct
22 Incorrect 2 ms 5212 KB 1st lines differ - on the 1st token, expected: '14', found: '12'
23 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5316 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 4 ms 5720 KB Output is correct
14 Correct 3 ms 5720 KB Output is correct
15 Correct 3 ms 5468 KB Output is correct
16 Correct 3 ms 5468 KB Output is correct
17 Correct 3 ms 5724 KB Output is correct
18 Correct 2 ms 5724 KB Output is correct
19 Correct 2 ms 5212 KB Output is correct
20 Correct 7 ms 11100 KB Output is correct
21 Correct 6 ms 10332 KB Output is correct
22 Correct 6 ms 10588 KB Output is correct
23 Correct 5 ms 11100 KB Output is correct
24 Correct 5 ms 11100 KB Output is correct
25 Correct 5 ms 11100 KB Output is correct
26 Correct 2 ms 4956 KB Output is correct
27 Correct 2 ms 4952 KB Output is correct
28 Correct 2 ms 4956 KB Output is correct
29 Incorrect 2 ms 5212 KB 1st lines differ - on the 1st token, expected: '14', found: '12'
30 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5316 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 4 ms 5720 KB Output is correct
14 Correct 3 ms 5720 KB Output is correct
15 Correct 3 ms 5468 KB Output is correct
16 Correct 3 ms 5468 KB Output is correct
17 Correct 3 ms 5724 KB Output is correct
18 Correct 2 ms 5724 KB Output is correct
19 Correct 2 ms 5212 KB Output is correct
20 Correct 7 ms 11100 KB Output is correct
21 Correct 6 ms 10332 KB Output is correct
22 Correct 6 ms 10588 KB Output is correct
23 Correct 5 ms 11100 KB Output is correct
24 Correct 5 ms 11100 KB Output is correct
25 Correct 5 ms 11100 KB Output is correct
26 Correct 5 ms 5464 KB Output is correct
27 Correct 125 ms 146888 KB Output is correct
28 Correct 109 ms 136788 KB Output is correct
29 Correct 78 ms 137808 KB Output is correct
30 Correct 87 ms 142928 KB Output is correct
31 Correct 88 ms 136028 KB Output is correct
32 Correct 89 ms 146768 KB Output is correct
33 Correct 83 ms 146828 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct
35 Correct 2 ms 4952 KB Output is correct
36 Correct 2 ms 4956 KB Output is correct
37 Incorrect 2 ms 5212 KB 1st lines differ - on the 1st token, expected: '14', found: '12'
38 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5316 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 4 ms 5720 KB Output is correct
14 Correct 3 ms 5720 KB Output is correct
15 Correct 3 ms 5468 KB Output is correct
16 Correct 3 ms 5468 KB Output is correct
17 Correct 3 ms 5724 KB Output is correct
18 Correct 2 ms 5724 KB Output is correct
19 Correct 2 ms 5212 KB Output is correct
20 Correct 7 ms 11100 KB Output is correct
21 Correct 6 ms 10332 KB Output is correct
22 Correct 6 ms 10588 KB Output is correct
23 Correct 5 ms 11100 KB Output is correct
24 Correct 5 ms 11100 KB Output is correct
25 Correct 5 ms 11100 KB Output is correct
26 Correct 5 ms 5464 KB Output is correct
27 Correct 125 ms 146888 KB Output is correct
28 Correct 109 ms 136788 KB Output is correct
29 Correct 78 ms 137808 KB Output is correct
30 Correct 87 ms 142928 KB Output is correct
31 Correct 88 ms 136028 KB Output is correct
32 Correct 89 ms 146768 KB Output is correct
33 Correct 83 ms 146828 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct
35 Correct 2 ms 4952 KB Output is correct
36 Correct 2 ms 4956 KB Output is correct
37 Incorrect 2 ms 5212 KB 1st lines differ - on the 1st token, expected: '14', found: '12'
38 Halted 0 ms 0 KB -