oj.uz

답안 #840612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840612 2023-08-31T14:27:57 Z arbuzick 봉쇄 시간 (IOI23_closing) C++17
37 / 100
 299 ms 51512 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 2e5 + 5;

constexpr long long inf = (long long)(1e18) + 7;

vector<pair<int, int>> g[maxn];

long long dist_x[maxn], dist_y[maxn];

int prv[maxn];

vector<int> path;

void dfs(int v, long long* dist) {
    for (auto [u, c] : g[v]) {
        if (u != prv[v]) {
            prv[u] = v;
            dist[u] = dist[v] + c;
            dfs(u, dist);
        }
    }
}

void calc_dist(int x, int y) {
    prv[x] = x;
    dfs(x, dist_x);
    prv[y] = y;
    dfs(y, dist_y);
    int nw = x;
    while (nw != y) {
        path.push_back(nw);
        nw = prv[nw];
    }
    path.push_back(y);
}

bool used[maxn];

constexpr int maxn2 = 505;

long long dp[maxn2][maxn2 * 2][4];

long long res[maxn2 * 2], pr_res[maxn2 * 2], suff_res[maxn2][maxn * 2];

int sz[maxn];

void calc_sz(int v, int prv) {
    sz[v] = 1;
    for (auto [u, c] : g[v]) {
        if (!used[u] && u != prv) {
            calc_sz(u, v);
            sz[v] += sz[u];
        }
    }
}

void calc_dp(int v, int prv) {
    int mx = 2;
    for (auto [u, c] : g[v]) {
        if (!used[u] && u != prv) {
            calc_dp(u, v);
            for (int mask = 0; mask < 4; ++mask) {
                for (int cnt_nw = mx; cnt_nw >= 0; --cnt_nw) {
                    if (dp[v][cnt_nw][mask] == inf) {
                        continue;
                    }
                    for (int cnt_add = 0; cnt_add <= sz[u] * 2 && cnt_nw + cnt_add <= sz[v] * 2; ++cnt_add) {
                        dp[v][cnt_nw + cnt_add][mask] = min(dp[v][cnt_nw + cnt_add][mask], dp[v][cnt_nw][mask] + dp[u][cnt_add][mask]);
                    }
                }
            }
            mx += sz[u] * 2;
        }
    }
    for (int cnt = 0; cnt <= sz[v] * 2; ++cnt) {
        dp[v][cnt][1] = min(dp[v][cnt][1], dp[v][cnt][0]);
        dp[v][cnt][2] = min(dp[v][cnt][2], dp[v][cnt][0]);
        dp[v][cnt][3] = min(dp[v][cnt][3], min(dp[v][cnt][1], dp[v][cnt][2]));
    }
}

int max_score(int n, int x, int y, long long k, vector<int> u,
              vector<int> v, vector<int> w) {
    path.clear();
    for (int i = 0; i < n; ++i) {
        g[i].clear();
        dist_x[i] = dist_y[i] = 0;
        used[i] = false;
    }
    for (int i = 0; i < n - 1; ++i) {
        g[u[i]].emplace_back(v[i], w[i]);
        g[v[i]].emplace_back(u[i], w[i]);
    }
    calc_dist(x, y);
    int ans = 0;
    long long k_old = k;
    multiset<long long> ms;
    for (int i = 0; i < n; ++i) {
        ms.insert(dist_x[i]);
        ms.insert(dist_y[i]);
    }
    while (!ms.empty() && *ms.begin() <= k) {
        k -= *ms.begin();
        ms.erase(ms.begin());
        ans++;
    }
    if (n > maxn2) {
        return ans;
    }
    for (int i = 0; i < n; ++i) {
        for (int cnt = 0; cnt < maxn2; ++cnt) {
            for (int mask = 0; mask < 4; ++mask) {
                dp[i][cnt][mask] = inf;
            }
        }
        dp[i][0][0] = 0;
        dp[i][1][1] = dist_x[i];
        dp[i][1][2] = dist_y[i];
        dp[i][2][3] = max(dist_x[i], dist_y[i]);
    }
    k = k_old;
    for (auto v : path) {
        used[v] = true;
    }
    for (auto v : path) {
        calc_sz(v, v);
        for (int cnt = 0; cnt <= sz[v] * 2; ++cnt) {
            for (int mask = 0; mask < 4; ++mask) {
                dp[v][cnt][mask] = inf;
            }
        }
        dp[v][0][0] = dp[v][0][1] = dp[v][0][2] = dp[v][0][3] = 0;
        calc_dp(v, v);
        // cout << "!" << ' ' << v << ' ' << dp[v][2][0] << ' ' << dp[v][2][1] << ' ' << dp[v][2][2] << ' ' << dp[v][2][3] << endl;
    }
    pr_res[0] = 0;
    for (int i = 1; i <= n * 2; ++i) {
        pr_res[i] = inf;
    }
    suff_res[path.size()][0] = 0;
    for (int i = 1; i <= n * 2; ++i) {
        suff_res[path.size()][i] = inf;
    }
    for (int i = (int)path.size() - 1; i >= 0; --i) {
        for (int cnt_nw = n * 2; cnt_nw >= 0; --cnt_nw) {
            suff_res[i][cnt_nw] = suff_res[i + 1][cnt_nw];
            if (suff_res[i + 1][cnt_nw] == inf) {
                continue;
            }
            for (int cnt_add = 0; cnt_add <= sz[path[i]] * 2 && cnt_nw + cnt_add <= n * 2; ++cnt_add) {
                suff_res[i][cnt_nw + cnt_add] = min(suff_res[i][cnt_nw + cnt_add], suff_res[i + 1][cnt_nw] + dp[path[i]][cnt_add][2]);
            }
        }
    }
    for (int l = 0; l < (int)path.size(); ++l) {
        for (int i = 0; i <= n * 2; ++i) {
            res[i] = pr_res[i];
        }
        for (int r = l + 1; r <= (int)path.size(); ++r) {
            int add_ans = 0;
            long long add_k = 0;
            for (int i = 0; i < l; ++i) {
                add_ans++;
                add_k += dist_x[path[i]];
            }
            for (int i = l; i < r; ++i) {
                add_ans += 2;
                add_k += max(dist_x[path[i]], dist_y[path[i]]);
                if (i == r - 1) {
                    for (int cnt_nw = n * 2; cnt_nw >= 0; --cnt_nw) {
                        if (res[cnt_nw] == inf) {
                            continue;
                        }
                        for (int cnt_add = 0; cnt_add <= sz[path[i]] * 2 && cnt_nw + cnt_add <= n * 2; ++cnt_add) {
                            res[cnt_nw + cnt_add] = min(res[cnt_nw + cnt_add], res[cnt_nw] + dp[path[i]][cnt_add][3]);
                        }
                    }
                }
            }
            for (int i = r; i < (int)path.size(); ++i) {
                add_ans++;
                add_k += dist_y[path[i]];
            }
            while (true) {
                bool change = false;
                if (add_k > k) {
                    break;
                }
                if (add_ans > ans) {
                    ans = add_ans;
                }
                for (int cnt = 0; cnt <= n * 2; ++cnt) {
                    while (ans < n * 2) {
                        if (res[cnt] + add_k + suff_res[r][ans + 1 - cnt - add_ans] <= k) {
                            change = true;
                            ans++;
                        } else {
                            break;
                        }
                    }
                }
                if (!change) {
                    break;
                }
            }
        }
        for (int cnt_nw = n * 2; cnt_nw >= 0; --cnt_nw) {
            if (pr_res[cnt_nw] == inf) {
                continue;
            }
            for (int cnt_add = 0; cnt_add <= sz[path[l]] * 2 && cnt_nw + cnt_add <= n * 2; ++cnt_add) {
                pr_res[cnt_nw + cnt_add] = min(pr_res[cnt_nw + cnt_add], pr_res[cnt_nw] + dp[path[l]][cnt_add][1]);
            }
        }
    }
    return ans;
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 45596 KB Output is correct
2 Correct 265 ms 51512 KB Output is correct
3 Correct 88 ms 7680 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5460 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5588 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 4 ms 5972 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6100 KB Output is correct
10 Correct 3 ms 6372 KB Output is correct
11 Correct 3 ms 6484 KB Output is correct

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5460 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5588 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 4 ms 5972 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6100 KB Output is correct
10 Correct 3 ms 6372 KB Output is correct
11 Correct 3 ms 6484 KB Output is correct
12 Correct 3 ms 6996 KB Output is correct
13 Correct 3 ms 6996 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 6996 KB Output is correct
16 Correct 5 ms 7900 KB Output is correct
17 Correct 6 ms 7996 KB Output is correct
18 Correct 4 ms 5588 KB Output is correct
19 Incorrect 9 ms 15572 KB 1st lines differ - on the 1st token, expected: '771', found: '1000'
20 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5460 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5588 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 4 ms 5972 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6100 KB Output is correct
10 Correct 3 ms 6372 KB Output is correct
11 Correct 3 ms 6484 KB Output is correct
12 Correct 3 ms 6996 KB Output is correct
13 Correct 3 ms 6996 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 4 ms 6996 KB Output is correct
16 Correct 5 ms 7900 KB Output is correct
17 Correct 6 ms 7996 KB Output is correct
18 Correct 4 ms 5588 KB Output is correct
19 Incorrect 9 ms 15572 KB 1st lines differ - on the 1st token, expected: '771', found: '1000'
20 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5460 KB Output is correct
5 Correct 2 ms 5588 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 5204 KB Output is correct
10 Correct 2 ms 5460 KB Output is correct
11 Correct 3 ms 5460 KB Output is correct
12 Correct 2 ms 5332 KB Output is correct
13 Correct 3 ms 5460 KB Output is correct
14 Correct 2 ms 5460 KB Output is correct
15 Correct 3 ms 5460 KB Output is correct
16 Correct 2 ms 5332 KB Output is correct
17 Correct 2 ms 5460 KB Output is correct
18 Correct 3 ms 5460 KB Output is correct
19 Correct 2 ms 5460 KB Output is correct
20 Correct 3 ms 5460 KB Output is correct
21 Correct 2 ms 5460 KB Output is correct
22 Correct 2 ms 5460 KB Output is correct
23 Correct 2 ms 5460 KB Output is correct
24 Correct 2 ms 5332 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5460 KB Output is correct
5 Correct 2 ms 5588 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 3 ms 6372 KB Output is correct
12 Correct 3 ms 6484 KB Output is correct
13 Correct 3 ms 6996 KB Output is correct
14 Correct 3 ms 6996 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 6996 KB Output is correct
17 Correct 5 ms 7900 KB Output is correct
18 Correct 6 ms 7996 KB Output is correct
19 Correct 2 ms 5076 KB Output is correct
20 Correct 2 ms 5076 KB Output is correct
21 Correct 2 ms 5204 KB Output is correct
22 Correct 2 ms 5460 KB Output is correct
23 Correct 3 ms 5460 KB Output is correct
24 Correct 2 ms 5332 KB Output is correct
25 Correct 3 ms 5460 KB Output is correct
26 Correct 2 ms 5460 KB Output is correct
27 Correct 3 ms 5460 KB Output is correct
28 Correct 2 ms 5332 KB Output is correct
29 Correct 2 ms 5460 KB Output is correct
30 Correct 3 ms 5460 KB Output is correct
31 Correct 2 ms 5460 KB Output is correct
32 Correct 3 ms 5460 KB Output is correct
33 Correct 2 ms 5460 KB Output is correct
34 Correct 2 ms 5460 KB Output is correct
35 Correct 2 ms 5460 KB Output is correct
36 Correct 2 ms 5332 KB Output is correct
37 Correct 2 ms 5460 KB Output is correct
38 Correct 3 ms 5972 KB Output is correct
39 Correct 4 ms 6996 KB Output is correct
40 Correct 3 ms 6996 KB Output is correct
41 Correct 4 ms 6996 KB Output is correct
42 Correct 3 ms 6996 KB Output is correct
43 Correct 4 ms 7636 KB Output is correct
44 Correct 3 ms 7124 KB Output is correct
45 Correct 4 ms 7448 KB Output is correct
46 Correct 3 ms 7124 KB Output is correct
47 Correct 3 ms 7124 KB Output is correct
48 Correct 3 ms 6740 KB Output is correct
49 Correct 3 ms 6100 KB Output is correct
50 Correct 3 ms 5460 KB Output is correct

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5460 KB Output is correct
5 Correct 2 ms 5588 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 3 ms 6372 KB Output is correct
12 Correct 3 ms 6484 KB Output is correct
13 Correct 3 ms 6996 KB Output is correct
14 Correct 3 ms 6996 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 6996 KB Output is correct
17 Correct 5 ms 7900 KB Output is correct
18 Correct 6 ms 7996 KB Output is correct
19 Correct 4 ms 5588 KB Output is correct
20 Incorrect 9 ms 15572 KB 1st lines differ - on the 1st token, expected: '771', found: '1000'
21 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5460 KB Output is correct
5 Correct 2 ms 5588 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 3 ms 6372 KB Output is correct
12 Correct 3 ms 6484 KB Output is correct
13 Correct 3 ms 6996 KB Output is correct
14 Correct 3 ms 6996 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 6996 KB Output is correct
17 Correct 5 ms 7900 KB Output is correct
18 Correct 6 ms 7996 KB Output is correct
19 Correct 4 ms 5588 KB Output is correct
20 Incorrect 9 ms 15572 KB 1st lines differ - on the 1st token, expected: '771', found: '1000'
21 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5460 KB Output is correct
4 Correct 2 ms 5460 KB Output is correct
5 Correct 2 ms 5588 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 4 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 3 ms 6372 KB Output is correct
12 Correct 3 ms 6484 KB Output is correct
13 Correct 3 ms 6996 KB Output is correct
14 Correct 3 ms 6996 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 6996 KB Output is correct
17 Correct 5 ms 7900 KB Output is correct
18 Correct 6 ms 7996 KB Output is correct
19 Correct 4 ms 5588 KB Output is correct
20 Incorrect 9 ms 15572 KB 1st lines differ - on the 1st token, expected: '771', found: '1000'
21 Halted 0 ms 0 KB -