oj.uz

Submission #856041

# Submission time Handle Problem Language Result Execution time Memory
856041 2023-10-02T15:29:31 Z Cyanmond Mousetrap (CEOI17_mousetrap) C++17
100 / 100
 806 ms 205748 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()

using i64 = long long;

void main_() {
    int N, T, M;
    cin >> N >> T >> M;
    --T, --M;
    if (T == M) {
        cout << 0 << endl;
        return;
    }

    vector<int> A(N - 1), B(N - 1);
    vector<vector<int>> Tree(N);
    rep(i, 0, N - 1) {
        cin >> A[i] >> B[i];
        Tree[--A[i]].push_back(--B[i]);
        Tree[B[i]].push_back(A[i]);
    }

    vector<bool> isPath(N);
    vector<int> path;
    auto dfs = [&](auto &&self, const int v, const int p) -> bool {
        bool ret = false;
        for (const int t : Tree[v]) {
            if (t == p) continue;
            ret |= self(self, t, v);
        }
        if (v == T) ret = true;
        isPath[v] = ret;
        if (ret) path.push_back(v);
        return ret;
    };
    dfs(dfs, M, -1);
    reverse(ALL(path));

    vector<int> dp(N);
    auto dfs2 = [&](auto &&self, const int v, const int p) -> int {
        vector<int> vals;
        for (const int t : Tree[v]) {
            if (t == p) continue;
            if (isPath[t]) continue;
            vals.push_back(self(self, t, v));
        }
        sort(ALL(vals), greater());
        int cost = -1;
        if (vals.empty()) cost = 0;
        else if (vals.size() == 1) cost = 1;
        else cost = vals[1] + (int)(vals.size()) - 1;
        dp[v] = cost;
        return dp[v] + 1;
    };
    for (const auto e : path) {
        if (e == T) continue;
        dfs2(dfs2, e, -1);
    }

    i64 ans = 1ll << 60;
    int S = (int)path.size();
    vector<int> rs(S);
    per(i, 1, S) {
        rs[i - 1] = rs[i] + (int)Tree[path[i - 1]].size() - 2;
    }
    vector<vector<int>> cList(S);
    rep(i, 0, S - 1) {
        vector<int> vals;
        for (const int t : Tree[path[i]]) {
            if (isPath[t]) continue;
            vals.push_back(dp[t]);
        }
        sort(ALL(vals), greater());
        rep(j, 0, (int)vals.size()) cList[i].push_back(vals[j] + (int)vals.size() - j);
    }


    

    int ok = 1 << 30, ng = -1;
    while (ok - ng > 1) {
        const auto m = (ok + ng) / 2;
        int cnt1 = 0;
        bool isOk = true;
        rep(i, 0, S - 1) {
            int baseCost = rs[i + 1];
            int lm1 = -1, lm2 = -1;
            rep(j, 0, (int)cList[i].size()) {
                if (lm1 == -1 and cnt1 + j + cList[i][j] + baseCost <= m) {
                    lm1 = j;
                }
                if (lm2 == -1 and cnt1 + j + cList[i][j] + 2 + baseCost <= m) {
                    lm2 = j;
                }
            }
            if (lm1 == -1 and cnt1 + cList[i].size() + baseCost <= m) lm1 = cList[i].size();
            if (lm2 != -1 and cnt1 + lm2 + 1 <= i + 1) {
                break;
            }
            if (lm1 == -1) {
                isOk = false;
                break;
            }
            cnt1 += lm1;
            if (cnt1 > i + 1) {
                isOk = false;
                break;
            }
        }
        (isOk ? ok : ng) = m;
    }

    cout << ok << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    main_();
}

Compilation message

mousetrap.cpp: In function 'void main_()':
mousetrap.cpp:101:65: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  101 |             if (lm1 == -1 and cnt1 + cList[i].size() + baseCost <= m) lm1 = cList[i].size();
      |                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mousetrap.cpp:65:9: warning: unused variable 'ans' [-Wunused-variable]
   65 |     i64 ans = 1ll << 60;
      |         ^~~

Subtask #1
20.0 / 20.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 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 608 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 66888 KB Output is correct
2 Correct 228 ms 66696 KB Output is correct
3 Correct 794 ms 75400 KB Output is correct
4 Correct 304 ms 37880 KB Output is correct
5 Correct 776 ms 75604 KB Output is correct
6 Correct 806 ms 75428 KB Output is correct

Subtask #3
20.0 / 20.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 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 608 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 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 0 ms 460 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct

Subtask #4
35.0 / 35.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 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 608 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 232 ms 66888 KB Output is correct
12 Correct 228 ms 66696 KB Output is correct
13 Correct 794 ms 75400 KB Output is correct
14 Correct 304 ms 37880 KB Output is correct
15 Correct 776 ms 75604 KB Output is correct
16 Correct 806 ms 75428 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 460 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 246 ms 80488 KB Output is correct
31 Correct 233 ms 80348 KB Output is correct
32 Correct 318 ms 145316 KB Output is correct
33 Correct 312 ms 205748 KB Output is correct
34 Correct 758 ms 81392 KB Output is correct
35 Correct 749 ms 81540 KB Output is correct
36 Correct 765 ms 90812 KB Output is correct
37 Correct 747 ms 90716 KB Output is correct
38 Correct 572 ms 92600 KB Output is correct
39 Correct 596 ms 92544 KB Output is correct
40 Correct 544 ms 92504 KB Output is correct