Submission #616593

#	Time	Username	Problem	Language	Result	Execution time	Memory
616593		BJoozz	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	326 ms	91908 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 lim2){
    //cout<<"here "<<v<<' '<<trc<<' '<<lim2<<'\n';

    int dem=pr[v].size()-1;
    if(lim2<dem){dp[v]=n;return;}
    for(int u:pr[v])if(u!=trc)
        go(u,v,lim2-dem);
    int cnt=0;
    for(int u:pr[v])if(u!=trc){
        if(dp[u]>=dem) cnt++;
        else B[dp[u]]++;
    }
    //if(dem<=lim2)
    dp[v]=dem;
    for(int i=dem-1;i>0;i--){
        //if(cnt<=lim2)
        minn(dp[v],i-1+cnt);
        //cout<<"haha "<<i<<' '<<cnt<<' '<<i-1+cnt<<'\n';
        cnt+=B[i];B[i]=0;
    }
    //if(cnt<=lim2)
    minn(dp[v],cnt);
    //cout<<"now "<<v<<' '<<dp[v]<<' '<<lim2<<'\n';
}
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++;
    //cout<<v<<' '<<val<<'\n';
    for(int u:pr[v])if(u!=trc && u!=z){
        dem++;
        go(u,v,lim-val);
    }
    if(dem==0){
        if(!GO(z,v,hav,lim))return 0;
        dp[v]=dp[z];return 1;
    }
    for(int u:pr[v])if(u!=trc && u!=z){
        if(dp[u]>hav+1) cnt++;
        else B[dp[u]]++;
        cout<<u<<' '<<dp[u]<<'\n';
    }
    ///(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<<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("mousetrap.inp","r",stdin);
    //freopen("mousetrap.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 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:117:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |         int mid=b+e>>1;
      |                 ~^~

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