Submission #616591

# Submission time Handle Problem Language Result Execution time Memory
616591 2022-08-01T05:35:12 Z BJoozz Mousetrap (CEOI17_mousetrap) C++14
0 / 100
16 ms 23892 KB
#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("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 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

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:111:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |         int mid=b+e>>1;
      |                 ~^~
mousetrap.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen("mousetrap.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen("mousetrap.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -