Submission #137032

#	Time	Username	Problem	Language	Result	Execution time	Memory
137032		thebes	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	574 ms	141308 KiB

mousetrap

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

const int MN = 2e6+6;
int n, s, t, i, x, y, p[MN], dp[MN], cost[MN], u[MN], d[MN], lo, hi;
vector<int> adj[MN], w[MN], path;
priority_queue<int> q;

void dfs(int n,int pp,int dd){
    p[n] = pp; d[n] = dd;
    for(auto v : adj[n]){
        if(v == pp) continue;
        dfs(v, n, dd+1);
    }
}

void prop(int n,int pp){
    if(pp){
        for(auto v : adj[n])
            if(!u[v]) cost[n]++;
        if(!u[pp]&&!u[n]) cost[n]--;
    }
    for(auto v : adj[n]){
        if(v != pp){
            cost[v] += cost[n];
            prop(v, n);
        }
    }
}

void solve(int n,int pp){
    int a=0, b=0;
    for(auto v : adj[n]){
        if(v==pp) continue;
        solve(v, n);
        if(dp[v]>a) b=a, a=dp[v];
        else if(dp[v]>b) b=dp[v];
    }
    dp[n]=max(b,cost[n]);
}

int main(){
    for(scanf("%d%d%d",&n,&t,&s),i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(s, 0, 1);
    for(i=t;i;i=p[i]){
        path.push_back(i);
        u[i] = 1;
        if(i==s) break;
    }
    prop(t, 0);
    for(auto v : path){
        if(v==t) continue;
        for(auto z : adj[v]){
            if(u[z]) continue;
            solve(z, v);
            w[d[v]].push_back(dp[z]);
        }
    }
    for(i=1;i<=n;i++)
        sort(w[i].begin(),w[i].end(),[](int i,int j){return i>j;});
    lo = cost[s], hi = n;
    while(lo<hi){
        int m = (lo+hi)/2;
        int ac=0, f=0, j, k;
        for(i=1;i<=n;i++){
            k=0;
            for(j=0;j<w[i].size();j++){
                if(w[i][j]-ac+j<=m){k=1; break;}
            }
            if(k) ac-=(j-1);
            else ac-=w[i].size();
            if(ac<0){f=1; break;}
        }
        if(f) lo=m+1;
        else hi=m;
    }
    printf("%d\n",lo);
    return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0;j<w[i].size();j++){
                     ~^~~~~~~~~~~~
mousetrap.cpp:43:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d%d",&n,&t,&s),i=1;i<n;i++){
         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mousetrap.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~

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