oj.uz

Submission #616706

# Submission time Handle Problem Language Result Execution time Memory
616706 2022-08-01T06:19:06 Z BJoozz Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 963 ms 158580 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("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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23816 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 15 ms 23816 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 14 ms 23816 KB Output is correct
6 Correct 13 ms 23812 KB Output is correct
7 Correct 16 ms 23764 KB Output is correct
8 Correct 14 ms 23816 KB Output is correct
9 Correct 13 ms 23752 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 76416 KB Output is correct
2 Correct 251 ms 72664 KB Output is correct
3 Correct 791 ms 81112 KB Output is correct
4 Correct 359 ms 52232 KB Output is correct
5 Correct 790 ms 81052 KB Output is correct
6 Correct 864 ms 81116 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23816 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 15 ms 23816 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 14 ms 23816 KB Output is correct
6 Correct 13 ms 23812 KB Output is correct
7 Correct 16 ms 23764 KB Output is correct
8 Correct 14 ms 23816 KB Output is correct
9 Correct 13 ms 23752 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 13 ms 23764 KB Output is correct
12 Correct 13 ms 23804 KB Output is correct
13 Correct 13 ms 23820 KB Output is correct
14 Correct 14 ms 23956 KB Output is correct
15 Correct 17 ms 23872 KB Output is correct
16 Correct 13 ms 23812 KB Output is correct
17 Correct 17 ms 23812 KB Output is correct
18 Correct 14 ms 23892 KB Output is correct
19 Correct 15 ms 23808 KB Output is correct
20 Correct 12 ms 23848 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Correct 12 ms 23864 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23816 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 15 ms 23816 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 14 ms 23816 KB Output is correct
6 Correct 13 ms 23812 KB Output is correct
7 Correct 16 ms 23764 KB Output is correct
8 Correct 14 ms 23816 KB Output is correct
9 Correct 13 ms 23752 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 351 ms 76416 KB Output is correct
12 Correct 251 ms 72664 KB Output is correct
13 Correct 791 ms 81112 KB Output is correct
14 Correct 359 ms 52232 KB Output is correct
15 Correct 790 ms 81052 KB Output is correct
16 Correct 864 ms 81116 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 13 ms 23804 KB Output is correct
19 Correct 13 ms 23820 KB Output is correct
20 Correct 14 ms 23956 KB Output is correct
21 Correct 17 ms 23872 KB Output is correct
22 Correct 13 ms 23812 KB Output is correct
23 Correct 17 ms 23812 KB Output is correct
24 Correct 14 ms 23892 KB Output is correct
25 Correct 15 ms 23808 KB Output is correct
26 Correct 12 ms 23848 KB Output is correct
27 Correct 12 ms 23892 KB Output is correct
28 Correct 12 ms 23864 KB Output is correct
29 Correct 12 ms 23808 KB Output is correct
30 Correct 282 ms 78252 KB Output is correct
31 Correct 291 ms 78228 KB Output is correct
32 Correct 916 ms 158580 KB Output is correct
33 Correct 370 ms 158552 KB Output is correct
34 Correct 796 ms 81180 KB Output is correct
35 Correct 822 ms 81072 KB Output is correct
36 Correct 906 ms 89784 KB Output is correct
37 Correct 963 ms 89764 KB Output is correct
38 Correct 708 ms 89048 KB Output is correct
39 Correct 667 ms 89092 KB Output is correct
40 Correct 667 ms 89108 KB Output is correct