Submission #705598

#	Time	Username	Problem	Language	Result	Execution time	Memory
705598		Kahou	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1748 ms	161896 KiB

mousetrap

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1e6 + 50;
ll n, t, m, val[N], dp[N], ps[N], k; 
bool mark[N];
vector<int> adj[N];
vector<int> vp;
vector<pii> vc;

void dfs(int u, int p=0) {
        if (u == t) return;
        int mx1 = 0, mx2 = 0;
        for (int v:adj[u]) {
                if (v == p) continue;
                dfs(v, u);
                if (mark[v]) {
                        mark[u] = 1;
                        val[u] = val[v] + (int)adj[u].size()-1-(p>0);
                }
                else {
                        if (dp[v] > mx1) {
                                mx2 = mx1;
                                mx1 = dp[v];
                        }
                        else if (dp[v] > mx2) {
                                mx2 = dp[v];
                        }
                }
        }
        if (!mark[u]) {
                dp[u] = (int)adj[u].size()-(p>0) + mx2;
        }
        else {
                vp.push_back(u);
                for (int v:adj[u]) {
                        if (v == p) continue;
                        if (mark[v]) continue;
                        vc.push_back({u, dp[v] + val[u]});
                }
        }
}

bool isval(ll x) {
        int id = 0;
        int tmp = 0;
        for (pii p:vc) {
                while (id < p.F) {
                        ps[id+1] = ps[id];
                        tmp = ps[id];
                        id++;
                }
                if (tmp+p.S > x) {
                        ps[id]++;
                }
        }
        for (int i = 1; i <= k; i++) {
                if (ps[i] > i || ps[i] > x) return 0;
        }
        return 1;
}
void solve() {
        cin >> n >> t >> m;
        for (int i = 1; i <= n-1; i++) {
                int u, v;
                cin >> u >> v;
                adj[u].push_back(v);
                adj[v].push_back(u);
        }
        mark[t] = 1;
        dfs(m);
        reverse(vp.begin(), vp.end());
        reverse(vc.begin(), vc.end());
        for (pii &x : vc) {
                while (x.F != vp[k]) k++;
                x.F = k+1;
                cerr << x.F << ' ' << x.S << endl;
        }
        k = vp.size();
        ll dw = -1, up = 1e9;
        while (up-dw > 1) {
                ll md = (up+dw)>>1;
                if (isval(md)) up = md;
                else dw = md;
        }
        cout << up << endl;
}

int main() {
        ios::sync_with_stdio(0), cin.tie(0);
        solve();
        return 0;
}

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