oj.uz

Submission #137035

# Submission time Handle Problem Language Result Execution time Memory
137035 2019-07-27T00:54:10 Z thebes Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 560 ms 94284 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 1e6+6;
int N, T, S, p[MN], dis[MN], dp[MN], u[MN], d[MN], m[MN], i, x, y;
vector<int> adj[MN], w[MN], path;

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 dfs2(int n,int pp){
    if(n != T){
        for(auto v : adj[n])
            if(!u[v]&&v!=pp) dis[n]++;
    }
    for(auto v : adj[n]){
        if(v != pp){
            dis[v] = dis[n];
            dfs2(v, n);
        }
    }
}

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

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;
    }
    dfs2(T, 0);
    for(auto v : path){
        m[d[v]] = dis[v];
        if(v == T) continue;
        for(auto a : adj[v]){
            if(u[a]) continue;
            dis[a] = 0;
            dfs2(a, v);
            dfs3(a, v);
            w[d[v]].push_back(dp[a]);
        }
    }
    for(i=1;i<=N;i++){
        sort(w[i].begin(),w[i].end(),[](int i,int j){return i>j;});
    }
    int lo=dis[S], hi=N;
    while(lo<hi){
        int mm=(lo+hi)/2;
        int ac=0, f=0, j, b=mm;
        for(i=1;i<=N;i++){
            for(j=-1;j+1<w[i].size();j++){
                if(w[i][j+1]+m[i]<=b-j-1) break;
            }
            ac-=j; b-=j+1;
            if(ac<0||b<0){
                f = 1; break;
            }
        }
        if(f) lo=mm+1;
        else hi=mm;
    }
    printf("%d\n",lo);
    return 0;
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:71:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=-1;j+1<w[i].size();j++){
                      ~~~^~~~~~~~~~~~
mousetrap.cpp:41: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:42: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.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 49 ms 47352 KB Output is correct
3 Correct 45 ms 47352 KB Output is correct
4 Correct 46 ms 47312 KB Output is correct
5 Correct 44 ms 47324 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 44 ms 47356 KB Output is correct
8 Correct 53 ms 47352 KB Output is correct
9 Incorrect 49 ms 47280 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 560 ms 94284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 49 ms 47352 KB Output is correct
3 Correct 45 ms 47352 KB Output is correct
4 Correct 46 ms 47312 KB Output is correct
5 Correct 44 ms 47324 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 44 ms 47356 KB Output is correct
8 Correct 53 ms 47352 KB Output is correct
9 Incorrect 49 ms 47280 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 49 ms 47352 KB Output is correct
3 Correct 45 ms 47352 KB Output is correct
4 Correct 46 ms 47312 KB Output is correct
5 Correct 44 ms 47324 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 44 ms 47356 KB Output is correct
8 Correct 53 ms 47352 KB Output is correct
9 Incorrect 49 ms 47280 KB Output isn't correct
10 Halted 0 ms 0 KB -