Submission #157224

#	Time	Username	Problem	Language	Result	Execution time	Memory
157224		lyc	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1086 ms	182320 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MX_N = 1e6+5;

int N, T, M, A, B;
vector<int> al[MX_N];
int w[MX_N], d[MX_N], pa[MX_N];
vector<ii> sub[MX_N];

void dfs(int u, int p) {
    for (auto v : al[u]) if (v != p) {
        pa[v] = u;
        d[v] = d[u] + 1;
        w[v] = w[u] + (p==0?0:SZ(al[u])-2);
        dfs(v,u);
    }
    if (SZ(al[u]) != 1) {
        int a = 0, b = 0;
        for (auto v : al[u]) if (v != p) {
            if (w[v] > a) b = a, a = w[v];
            else if (w[v] > b) b = w[v];
        }
        if (b) w[u] = b;
        else w[u] += d[u]+1;
    } else w[u] += d[u];
    //cout << u << " :: " << w[u] << " " << d[u] << "\n";
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> T >> M;
    FOR(i,1,N-1){
        cin >> A >> B;
        al[A].push_back(B);
        al[B].push_back(A);
    }

    dfs(T,0);
    int lo = -1, hi = 2*N;
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;

        int p, u, i, b, bad = 0;
        for (p = -1, u = M, i = 0, b = 0; pa[u] != 0; p = u, u = pa[u], ++i) {
            //cout << "\tTRAVERSE " << u << endl;
            int x = 0;
            for (int v : al[u]) if (v != pa[u] && v != p) {
                //cout << "\t\tNEI " << v << " :: " << w[v]-(u!=M)-d[u] << endl;
                if (w[v]-(u!=M)-d[u]+b > mid) ++x;
            }
            b += x;
            if (b > i+1) bad = 1;
        }
        if (b > mid) bad = 1;

        //cout << mid << " :: " << bad << endl;
        (bad ? lo : hi) = mid;
    }

    cout << hi << '\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35