Submission #1110933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110933		haianhnguyen08102007	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	537 ms	162648 KiB

mousetrap

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }

using namespace std;

const int N = 1e6 + 5;
const int inf = 1e18;

vector <int> adj[N];
int n, t, m, dp[N], par[N];

void dfs(int pos, int prev)
{
    if (prev != -1)
        adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), prev));
    int mx = 0, sc = 0;
    for (auto x : adj[pos])
    {
        par[x] = pos;
        dfs(x, pos);
        if (dp[x] >= mx) sc = mx, mx = dp[x];
        else sc = max(sc, dp[x]);
    }
    dp[pos] = sc + adj[pos].size();
}

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

    cin>>n>>t>>m;
    t--; m--;
    for (int i=0; i<n-1; i++)
    {
        int a, b; cin>>a>>b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(t, -1);
    int ttld = 0, l = -1, r = n;
    while (l + 1 < r)
    {
        int mid = (l+r)/2, ok = 1, dif = 0, prev = -1, canuse = 0, cur = m, used = 0;
        while (cur != t)
        {
            canuse++; int tmp = 0;
            for (auto x:adj[cur])
            {
                if (x==prev) continue;
                if (dp[x] - dif + used > mid)
                {
                    if (!canuse) ok = 0;
                    else canuse--, tmp++;
                }
            }
            used += tmp, dif += adj[cur].size() - (prev != -1);
            prev = cur, cur = par[cur];
        }
        ttld = dif;
        if (ok) r = mid;
        else l = mid;
    }

    cout<<r + ttld;

    return 0;
}

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