oj.uz

Submission #151719

# Submission time Handle Problem Language Result Execution time Memory
151719 2019-09-04T11:04:31 Z forestryks Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 1365 ms 164732 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int MAXN = 1e6 + 5;
int n, t, m;
vector<int> g[MAXN];
int p[MAXN];
bool onp[MAXN];
int h[MAXN];
int sum[MAXN];
int dp[MAXN];

bool pre(int v) {
    for (auto to : g[v]) {
        g[to].erase(find(all(g[to]), v));
        p[to] = v;
        h[to] = h[v] + 1;
        if (pre(to)) {
            onp[v] = true;
        }
    }

    if (v == m || onp[v]) return (onp[v] = true);
    return false;
}

void dfs(int v) {
    sum[v] += g[v].size();
    for (auto to : g[v]) {
        sum[to] += sum[v];
    }

    int mx1 = -1, mx2 = -1;
    for (auto to : g[v]) {
        dfs(to);
        if (dp[to] > mx2) {
            if (dp[to] > mx1) {
                mx2 = mx1;
                mx1 = dp[to];
            } else {
                mx2 = dp[to];
            }
        }
    }

    if (g[v].empty()) {
        dp[v] = 0;
    } else if (mx2 == -1) {
        dp[v] = 1;
    } else {
        dp[v] = mx2 + g[v].size();
    }
}

vector<int> ord;
bool used[MAXN];

bool check(int x) {
    memset(used, 0, sizeof used);
    ord.clear();
    ord.reserve(n);
    int cnt = 0;
    for (int v = m; v != t; v = p[v]) {
        int cnt1 = 0;
        for (auto to : g[v]) {
            if (onp[to]) continue;
            int c = cnt + dp[to] + (sum[v] - h[v] - (v != m));
            if (c > x) {
                ord.push_back(to);
                cnt1++;
            } else {
                used[to] = true;
            }
        }
        cnt += cnt1;
    }

    int ptr = 0;
    for (int v = m; v != t; v = p[v]) {
        if (ptr < ord.size()) {
            used[ord[ptr++]] = true;
        }

        for (auto to : g[v]) {
            if (onp[to]) continue;
            if (!used[to]) return false;
        }
    }

    return (cnt <= x);
}

int main() {
    FAST_IO;
    cin >> n >> t >> m;
    t--; m--;
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    p[t] = -1;
    pre(t);
    dfs(t);

    int l = -1, r = 1e7;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (check(m)) {
            r = m;
        } else {
            l = m;
        }
    }

    cout << r << endl;

    // cout << check(0) << endl;
}

Compilation message

mousetrap.cpp: In function 'bool check(int)':
mousetrap.cpp:87:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ptr < ord.size()) {
             ~~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24824 KB Output is correct
2 Correct 25 ms 24824 KB Output is correct
3 Correct 26 ms 24824 KB Output is correct
4 Correct 25 ms 24828 KB Output is correct
5 Correct 26 ms 24828 KB Output is correct
6 Correct 26 ms 24876 KB Output is correct
7 Correct 26 ms 24824 KB Output is correct
8 Correct 26 ms 24824 KB Output is correct
9 Correct 26 ms 24824 KB Output is correct
10 Correct 25 ms 24824 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 71824 KB Output is correct
2 Correct 399 ms 67108 KB Output is correct
3 Correct 1106 ms 72820 KB Output is correct
4 Correct 488 ms 48888 KB Output is correct
5 Correct 1079 ms 72832 KB Output is correct
6 Correct 1083 ms 72952 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24824 KB Output is correct
2 Correct 25 ms 24824 KB Output is correct
3 Correct 26 ms 24824 KB Output is correct
4 Correct 25 ms 24828 KB Output is correct
5 Correct 26 ms 24828 KB Output is correct
6 Correct 26 ms 24876 KB Output is correct
7 Correct 26 ms 24824 KB Output is correct
8 Correct 26 ms 24824 KB Output is correct
9 Correct 26 ms 24824 KB Output is correct
10 Correct 25 ms 24824 KB Output is correct
11 Correct 26 ms 24824 KB Output is correct
12 Correct 25 ms 24824 KB Output is correct
13 Correct 27 ms 24824 KB Output is correct
14 Correct 26 ms 24952 KB Output is correct
15 Correct 27 ms 24952 KB Output is correct
16 Correct 26 ms 24824 KB Output is correct
17 Correct 26 ms 24824 KB Output is correct
18 Correct 26 ms 24952 KB Output is correct
19 Correct 27 ms 24824 KB Output is correct
20 Correct 26 ms 24824 KB Output is correct
21 Correct 27 ms 24900 KB Output is correct
22 Correct 26 ms 24824 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24824 KB Output is correct
2 Correct 25 ms 24824 KB Output is correct
3 Correct 26 ms 24824 KB Output is correct
4 Correct 25 ms 24828 KB Output is correct
5 Correct 26 ms 24828 KB Output is correct
6 Correct 26 ms 24876 KB Output is correct
7 Correct 26 ms 24824 KB Output is correct
8 Correct 26 ms 24824 KB Output is correct
9 Correct 26 ms 24824 KB Output is correct
10 Correct 25 ms 24824 KB Output is correct
11 Correct 443 ms 71824 KB Output is correct
12 Correct 399 ms 67108 KB Output is correct
13 Correct 1106 ms 72820 KB Output is correct
14 Correct 488 ms 48888 KB Output is correct
15 Correct 1079 ms 72832 KB Output is correct
16 Correct 1083 ms 72952 KB Output is correct
17 Correct 26 ms 24824 KB Output is correct
18 Correct 25 ms 24824 KB Output is correct
19 Correct 27 ms 24824 KB Output is correct
20 Correct 26 ms 24952 KB Output is correct
21 Correct 27 ms 24952 KB Output is correct
22 Correct 26 ms 24824 KB Output is correct
23 Correct 26 ms 24824 KB Output is correct
24 Correct 26 ms 24952 KB Output is correct
25 Correct 27 ms 24824 KB Output is correct
26 Correct 26 ms 24824 KB Output is correct
27 Correct 27 ms 24900 KB Output is correct
28 Correct 26 ms 24824 KB Output is correct
29 Correct 26 ms 24824 KB Output is correct
30 Correct 462 ms 85120 KB Output is correct
31 Correct 455 ms 85412 KB Output is correct
32 Correct 839 ms 164732 KB Output is correct
33 Correct 513 ms 163664 KB Output is correct
34 Correct 1206 ms 86208 KB Output is correct
35 Correct 1079 ms 86260 KB Output is correct
36 Correct 1324 ms 94924 KB Output is correct
37 Correct 1365 ms 94848 KB Output is correct
38 Correct 995 ms 97328 KB Output is correct
39 Correct 997 ms 97276 KB Output is correct
40 Correct 937 ms 97304 KB Output is correct