Submission #616706

#	Time	Username	Problem	Language	Result	Execution time	Memory
616706		BJoozz	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	963 ms	158580 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
//#define int long long
void maxx(int &a,int b){if(b>a) a=b;}
void minn(int &a,int b){if(b<a) a=b;}

using ll = long long;
using ii = pair < int , int >;
const int MAX=1e6+3,inf=1e9,mod=1e9+7;
vector < int > pr[MAX];
//int tim=0,sz[MAX];
int pa[MAX];
int n;
int H[MAX];
void dfs(int v,int trc){
    for(int u:pr[v])if(u!=trc){
        pa[u]=v;
        H[u]=H[v]+pr[u].size()-2;
        dfs(u,v);
    }
}
int dp[MAX];
int B[MAX];
void go(int v,int trc){
    int S1=0,S2=-1;
    for(int u:pr[v])if(u!=trc){
        go(u,v);
        dp[v]++;
        if(S1<dp[u]){
            S2=S1;S1=dp[u];
        }else{
            maxx(S2,dp[u]);
        }
    }
    if(dp[v]>1) {
        dp[v]+=S2;
    }
}
int t;
//int lim;
bool GO(int v,int trc,int hav,int lim){
    dp[v]=0;
    if(v==t) return 1;
    int z=pa[v];

    int dem=0,cnt=0;
    int val=H[v];
    hav++;
    for(int u:pr[v])if(u!=trc && u!=z){
        if(dp[u]+val>lim) cnt++;
        else B[dp[u]+val]++;
        dem++;
    }
    if(dem==0){
        if(!GO(z,v,hav,lim))return 0;
        dp[v]=dp[z];return 1;
    }

    ///(hav-need+1<dp[u])<=need;
    //cout<<cnt<<' '<<need<<'\n';
    int need=0;
    while(need <dem && cnt>need){
        if(hav-need+1>=0) cnt+=B[hav-need+1];
        need++;
    }
    for(int u:pr[v])B[dp[u]]=0;
    //cout<<lim<<' '<<need<<'\n';

    cnt=need;
    //cout<<"st "<<v<<' '<<hav<<' '<<cnt<<' '<<lim<<'\n';
    lim-=cnt;
    if(hav<cnt)return 0;
    if(!GO(z,v,hav-cnt,lim))return 0;
    dp[v]=dp[z]+cnt;
    return 1;
}
int m;
bool ok(int val){
    int lim=val;
    if(!GO(m,0,0,lim))return 0;
    //cout<<val<<' '<<m<<' '<<dp[m]<<'\n';
    return dp[m]<=lim;
}
signed main(){
    //freopen("2.inp","r",stdin);
    //freopen("2.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n>>t>>m ;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        pr[x].pb(y);
        pr[y].pb(x);
    }
    dfs(t,0);

    int x=m,pre=0;
    while(x!=t){
        for(int u:pr[x])if(u!=pre && u!=pa[x])
            go(u,x);
        pre=x;
        x=pa[x];
    }

    int b=0,e=n-1,ans=n;
    H[m]++;
    //cout<<ok(5);return 0;
    while(b<=e){
        int mid=b+e>>1;
        if(ok(mid)){
            ans=mid;e=mid-1;
        }else b=mid+1;
    }


    cout<<ans;
}

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:111:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |         int mid=b+e>>1;
      |                 ~^~

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