oj.uz

Submission #571532

# Submission time Handle Problem Language Result Execution time Memory
571532 2022-06-02T10:38:02 Z piOOE Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 381 ms 83480 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int N = 1000001, infI = 1e9 + 7;
const ll infL = 3e18;

int n, t, m;
vector<int> g[N];
int dp[N], parent[N], depth[N], deg[N], gg[N], sum_deg[N];
vector<int> tops;

void dfs(int v, int p) {
    parent[v] = p;
    int mx1 = 0, mx2 = 0;
    deg[v] = (p == v ? sz(g[v]) : sz(g[v]) - 1);
    sum_deg[v] = sum_deg[p] + deg[v];
    for (int to: g[v]) {
        if (to != p) {
            depth[to] = depth[v] + 1;
            dfs(to, v);
            if (mx1 < dp[to]) {
                mx2 = mx1;
                mx1 = dp[to];
            } else if (mx2 < dp[to]) {
                mx2 = dp[to];
            }
        }
    }
    dp[v] = mx2 + deg[v];
    tops.push_back(v);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> t >> m;
    --t, --m;
    if (t == m) {
        cout << 0;
        return 0;
    }
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(t, t);
//    cout << "dp:\n";
//    for (int i = 0; i < n; ++i) cout << dp[i] << " ";
//    cout << endl;
    memset(gg, -1, sizeof(gg));
//    trace(sum_deg[m] - depth[m])
    {
        int x = m, prv = -1;
        while (x != t) {
            for (int to: g[x]) {
                if (to != parent[x] && to != prv) {
                    gg[to] = dp[to] + (x == m ? sum_deg[x] - depth[x] : sum_deg[x] - depth[x] - 1);
//                    cout << to << " " << gg[to] << endl;
                }
            }
            prv = x;
            x = parent[x];
        }
    }
    int ans = infI;
    int l = -1, r = infI;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        vector<int> pos;
        vector<bool> used(n);
        for (int x: tops) {
            if (gg[x] > mid) {
                pos.push_back(x);
            }
        }
        int x = m;
        int pnt = 0;
        bool ok = true;
        while (x != t) {
            if (pnt < sz(pos)) {
                used[pos[pnt++]] = true;
            }
            for (int to: g[x]) {
                if (to != parent[x] && gg[to] > mid && !used[to]) {
                    ok = false;
                    break;
                }
            }
            if (!ok) {
                break;
            }
            x = parent[x];
        }
        if (ok) {
            ans = min(ans, mid + pnt);
            r = mid;
        } else {
            l = mid;
        }
    }

    cout << ans;
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27716 KB Output is correct
2 Correct 17 ms 27644 KB Output is correct
3 Correct 14 ms 27660 KB Output is correct
4 Correct 16 ms 27660 KB Output is correct
5 Correct 18 ms 27644 KB Output is correct
6 Correct 15 ms 27656 KB Output is correct
7 Correct 16 ms 27652 KB Output is correct
8 Correct 17 ms 27652 KB Output is correct
9 Incorrect 19 ms 27656 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27716 KB Output is correct
2 Correct 17 ms 27644 KB Output is correct
3 Correct 14 ms 27660 KB Output is correct
4 Correct 16 ms 27660 KB Output is correct
5 Correct 18 ms 27644 KB Output is correct
6 Correct 15 ms 27656 KB Output is correct
7 Correct 16 ms 27652 KB Output is correct
8 Correct 17 ms 27652 KB Output is correct
9 Incorrect 19 ms 27656 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 27716 KB Output is correct
2 Correct 17 ms 27644 KB Output is correct
3 Correct 14 ms 27660 KB Output is correct
4 Correct 16 ms 27660 KB Output is correct
5 Correct 18 ms 27644 KB Output is correct
6 Correct 15 ms 27656 KB Output is correct
7 Correct 16 ms 27652 KB Output is correct
8 Correct 17 ms 27652 KB Output is correct
9 Incorrect 19 ms 27656 KB Output isn't correct
10 Halted 0 ms 0 KB -