oj.uz

Submission #856039

# Submission time Handle Problem Language Result Execution time Memory
856039 2023-10-02T15:22:34 Z Cyanmond Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 221 ms 74448 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;
    };

    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]);
        }
        rep(j, 0, (int)vals.size()) cList[i].push_back(vals[j] + (int)vals.size() - j);
    }

    /*
    rep(i, 0, S) {
        for (const auto e : cList[i]) cerr << e << ' ';
        cerr << endl;
    }
    */

    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] + 1 + baseCost <= m) {
                    lm1 = j;
                }
                if (lm2 == -1 and cnt1 + j + cList[i][j] + 3 + 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:100:65: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  100 |             if (lm1 == -1 and cnt1 + cList[i].size() + baseCost <= m) lm1 = cList[i].size();
      |                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mousetrap.cpp:45:10: warning: variable 'dfs2' set but not used [-Wunused-but-set-variable]
   45 |     auto dfs2 = [&](auto &&self, const int v, const int p) -> int {
      |          ^~~~
mousetrap.cpp:61:9: warning: unused variable 'ans' [-Wunused-variable]
   61 |     i64 ans = 1ll << 60;
      |         ^~~

Subtask #1
0 / 20.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 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 74448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.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 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.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 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -