Submission #563713

#	Time	Username	Problem	Language	Result	Execution time	Memory
563713		hoanghq2004	Mousetrap (CEOI17_mousetrap)	C++14	45 / 100	792 ms	87592 KiB

mousetrap

#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 (stderr)

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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35