Submission #320678

#	Time	Username	Problem	Language	Result	Execution time	Memory
320678		phathnv	Mousetrap (CEOI17_mousetrap)	C++11	100 / 100	3202 ms	159652 KiB

mousetrap

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e6 + 1;

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

int dp[N], par[N], h[N], b[N];
bool inPath[N];
vector <ii> d;

void readInput(){
    scanf("%d %d %d", &n, &t, &m);
    for(int i = 1; i < n; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void dfs(int u, int p){
    for(int v : adj[u])
        if (v != p){
            par[v] = u;
            h[v] = h[u] + 1;
            dfs(v, u);
            inPath[u] |= inPath[v];
        }
}

void calcDp(int u, int p){
    if (inPath[u]){
        dp[u] = -1;
        for(int v : adj[u])
            if (v != p)
                calcDp(v, u);
        return;
    }

    dp[u] = 0;
    int nChild = 0, max1 = 0, max2 = 0;
    for(int v : adj[u])
        if (v != p && !inPath[v]){
            nChild++;
            calcDp(v, u);
            max2 = max(max2, dp[v]);
            if (max1 < max2)
                swap(max1, max2);
        }
    dp[u] = max2 + nChild;
}

void prepare(){
    inPath[m] = 1;
    dfs(t, -1);
    inPath[m] = 0;
    calcDp(t, -1);
    inPath[m] = 1;

    int u = -1, cnt = 0;
    for(int v : adj[t])
        if (v != par[t] && inPath[v])
            u = v;
    while (u != -1){
        for(int v : adj[u])
            if (v != par[u] && !inPath[v])
                cnt++;
        for(int v : adj[u])
            if (v != par[u] && !inPath[v])
                d.push_back(mp(h[m] - h[u] + 1, dp[v] + cnt));
        int nxt = -1;
        for(int v : adj[u])
            if (v != par[u] && inPath[v])
                nxt = v;
        u = nxt;
    }

    sort(d.begin(), d.end(), [](const ii &a, const ii &b){
            if (a.X != b.X)
                return a.X < b.X;
            return a.Y > b.Y;
         });
}

bool check(int x){
    int blocked = 0, cnt = 0, cur = 0;
    for(ii p : d){
        if (p.X != cur){
            blocked += cnt;
            cur = p.X;
            cnt = 0;
        }
        if (p.Y + blocked > x){
            if (blocked + cnt < min(x, p.X))
                cnt++;
            else
                return 0;
        }
    }
    return 1;
}

void solve(){
    cerr << "d: " << endl;
    for(ii p : d)
        cerr << p.X << ' ' << p.Y << endl;
    int l = 0, r = n - 1, res = -1;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (check(mid)){
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    printf("%d", res);
}

int main(){
    readInput();
    prepare();
    solve();
    return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'void readInput()':
mousetrap.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%d %d %d", &n, &t, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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