oj.uz

Submission #1106534

# Submission time Handle Problem Language Result Execution time Memory
1106534 2024-10-30T15:07:11 Z LOLOLO Mousetrap (CEOI17_mousetrap) C++14
40 / 100
 198 ms 62536 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e6 + 10;
vector <int> ed[N];
int f[N], n, m, t, on[N], dep[N];

void dfs(int u, int v) {
    vector <int> cost;
    for (auto x : ed[u]) {
        if (x == v)
            continue;

        if (v) {
            f[x] = f[u] + sz(ed[u]) - 2;
        }

        dfs(x, u);
        if (on[x])
            on[u] = 1;

        cost.pb(f[x]);
    }

    sort(all(cost));
    if (sz(cost) > 1) {
        f[u] = cost[1];
    }

    f[u] += (sz(ed[u]) > 1);
}

vector <pair <int, int>> save;

void run(int u, int v) {
    if (u == t)
        return;

    for (auto x : ed[u]) {
        if (x == v)
            continue;

        dep[x] = dep[u] + 1;
        if (on[u] && !on[x]) {
            save.pb({dep[x], f[x] + (u == m)});
        } else {
            run(x, u);
        }
    }
}

bool check(int m) {
    int need = 0;
    for (auto x : save) {
        if (need > x.f)
            return 0;

        if (need + x.s > m) {
            need++;
        }
    }

    return need <= m;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> t >> m;

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ed[a].pb(b);
        ed[b].pb(a);
    }

    on[m] = 1;
    dep[m] = -1;

    dfs(t, 0);
    run(m, 0);
    sort(all(save));

    int l = 0, r = n, ans = 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (check(m)) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 5 ms 29264 KB Output is correct
3 Correct 5 ms 29264 KB Output is correct
4 Correct 6 ms 29264 KB Output is correct
5 Correct 6 ms 29520 KB Output is correct
6 Correct 6 ms 29264 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 6 ms 29264 KB Output is correct
9 Correct 5 ms 29516 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 5 ms 29264 KB Output is correct
3 Correct 5 ms 29264 KB Output is correct
4 Correct 6 ms 29264 KB Output is correct
5 Correct 6 ms 29520 KB Output is correct
6 Correct 6 ms 29264 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 6 ms 29264 KB Output is correct
9 Correct 5 ms 29516 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct
11 Correct 6 ms 29264 KB Output is correct
12 Correct 5 ms 29264 KB Output is correct
13 Correct 6 ms 29320 KB Output is correct
14 Correct 5 ms 29264 KB Output is correct
15 Correct 5 ms 29264 KB Output is correct
16 Correct 6 ms 29264 KB Output is correct
17 Correct 6 ms 29264 KB Output is correct
18 Correct 6 ms 29264 KB Output is correct
19 Correct 5 ms 29264 KB Output is correct
20 Correct 6 ms 29264 KB Output is correct
21 Correct 6 ms 29520 KB Output is correct
22 Correct 5 ms 29264 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29264 KB Output is correct
2 Correct 5 ms 29264 KB Output is correct
3 Correct 5 ms 29264 KB Output is correct
4 Correct 6 ms 29264 KB Output is correct
5 Correct 6 ms 29520 KB Output is correct
6 Correct 6 ms 29264 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 6 ms 29264 KB Output is correct
9 Correct 5 ms 29516 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct
11 Incorrect 198 ms 62536 KB Output isn't correct
12 Halted 0 ms 0 KB -