oj.uz

Submission #563713

# Submission time Handle Problem Language Result Execution time Memory
563713 2022-05-18T03:39:43 Z hoanghq2004 Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 792 ms 87592 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, S, T;
vector <int> g[N];
int f[N], flag[N];

void dfs(int u, int p) {
    int best[3] = {0, 0, 0};
    for (auto v: g[u]) {
        if (v == p) continue;
        dfs(v, u);
        best[2] = f[v];
        sort(best, best + 3);
        reverse(best, best + 3);
    }
    f[u] = best[1] + g[u].size() - 1;
}

int par[N];

void init(int u, int p) {
    par[u] = p;
    for (auto v: g[u]) {
        if (v == p) continue;
        init(v, u);
    }
}

vector <int> s[N];

int main() {
//    freopen("mousetrap.inp", "r", stdin);
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> T >> S;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    init(S, 0);
    vector <int> path;
    for (int u = T; u != S; u = par[u]) flag[par[u]] = 1, path.push_back(par[u]);
    reverse(path.begin(), path.end());
    int need = 0;
    for (auto u: path) {
        for (auto v: g[u]) {
            if (flag[v]) continue;
            if (v == T) continue;
            ++need;
            dfs(v, u);
            s[u].push_back(f[v]);
        }
    }
    for (int u = 1; u <= n; ++u) {
        sort(s[u].begin(), s[u].end());
        reverse(s[u].begin(), s[u].end());
    }
    auto check = [&](int limit) {
        int k = 0, tot = 0;
        for (auto u: path) {
            ++k;
            int i = 0;
            while (i < s[u].size() && s[u][i] + need > limit) {
                --k;
                if (k < 0) return 0;
                ++tot;
                ++i;
            }
        }
        if (tot > limit) return 0;
        return 1;
    };
    int L = need, R = n;
    while (L < R) {
        int mid = L + R >> 1;
        if (check(mid)) R = mid;
        else L = mid + 1;
    }
    cout << L;
}

Compilation message

mousetrap.cpp: In lambda function:
mousetrap.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             while (i < s[u].size() && s[u][i] + need > limit) {
      |                    ~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = L + R >> 1;
      |                   ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 23 ms 47180 KB Output is correct
4 Correct 23 ms 47272 KB Output is correct
5 Correct 24 ms 47220 KB Output is correct
6 Correct 23 ms 47308 KB Output is correct
7 Correct 22 ms 47188 KB Output is correct
8 Correct 22 ms 47188 KB Output is correct
9 Correct 25 ms 47180 KB Output is correct
10 Correct 22 ms 47244 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 86360 KB Output is correct
2 Correct 271 ms 82548 KB Output is correct
3 Correct 781 ms 87516 KB Output is correct
4 Correct 381 ms 67416 KB Output is correct
5 Correct 792 ms 87444 KB Output is correct
6 Correct 792 ms 87592 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 23 ms 47180 KB Output is correct
4 Correct 23 ms 47272 KB Output is correct
5 Correct 24 ms 47220 KB Output is correct
6 Correct 23 ms 47308 KB Output is correct
7 Correct 22 ms 47188 KB Output is correct
8 Correct 22 ms 47188 KB Output is correct
9 Correct 25 ms 47180 KB Output is correct
10 Correct 22 ms 47244 KB Output is correct
11 Correct 22 ms 47180 KB Output is correct
12 Correct 22 ms 47316 KB Output is correct
13 Correct 22 ms 47316 KB Output is correct
14 Correct 24 ms 47372 KB Output is correct
15 Correct 29 ms 47260 KB Output is correct
16 Incorrect 23 ms 47444 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 23 ms 47180 KB Output is correct
4 Correct 23 ms 47272 KB Output is correct
5 Correct 24 ms 47220 KB Output is correct
6 Correct 23 ms 47308 KB Output is correct
7 Correct 22 ms 47188 KB Output is correct
8 Correct 22 ms 47188 KB Output is correct
9 Correct 25 ms 47180 KB Output is correct
10 Correct 22 ms 47244 KB Output is correct
11 Correct 286 ms 86360 KB Output is correct
12 Correct 271 ms 82548 KB Output is correct
13 Correct 781 ms 87516 KB Output is correct
14 Correct 381 ms 67416 KB Output is correct
15 Correct 792 ms 87444 KB Output is correct
16 Correct 792 ms 87592 KB Output is correct
17 Correct 22 ms 47180 KB Output is correct
18 Correct 22 ms 47316 KB Output is correct
19 Correct 22 ms 47316 KB Output is correct
20 Correct 24 ms 47372 KB Output is correct
21 Correct 29 ms 47260 KB Output is correct
22 Incorrect 23 ms 47444 KB Output isn't correct
23 Halted 0 ms 0 KB -