oj.uz

Submission #137030

# Submission time Handle Problem Language Result Execution time Memory
137030 2019-07-26T23:12:20 Z thebes Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 1334 ms 143884 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 2e6+6;
int n, s, t, i, x, y, p[MN], dp[MN], cost[MN], u[MN], d[MN], lo, hi;
vector<int> adj[MN], w[MN], path;
priority_queue<int> q;

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

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

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;
        if(i==s) break;
    }
    prop(t, 0);
    for(auto v : path){
        if(v==t) continue;
        for(auto z : adj[v]){
            if(u[z]) continue;
            solve(z, v);
            w[d[v]].push_back(dp[z]);
        }
    }
    for(i=1;i<=n;i++)
        sort(w[i].begin(),w[i].end(),[](int i,int j){return i>j;});
    lo = cost[s], hi = n;
    while(lo<hi){
        int m = (lo+hi)/2;
        int ac=0, f=0, j;
        for(i=1;i<=n;i++){
            for(j=0;j<w[i].size();j++){
                if(w[i][j]-max(0,ac)<=m) break;
                else ac--;
            }
            ac++;
            if(ac<0){f=1; break;}
        }
        if(f) lo=m+1;
        else hi=m;
    }
    printf("%d\n",lo);
    return 0;
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0;j<w[i].size();j++){
                     ~^~~~~~~~~~~~
mousetrap.cpp:43: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:44: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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 94328 KB Output is correct
2 Correct 87 ms 94328 KB Output is correct
3 Correct 88 ms 94328 KB Output is correct
4 Correct 87 ms 94328 KB Output is correct
5 Correct 87 ms 94248 KB Output is correct
6 Correct 87 ms 94328 KB Output is correct
7 Correct 87 ms 94328 KB Output is correct
8 Correct 87 ms 94328 KB Output is correct
9 Correct 87 ms 94328 KB Output is correct
10 Correct 88 ms 94328 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 141404 KB Output is correct
2 Correct 519 ms 138052 KB Output is correct
3 Correct 1334 ms 143884 KB Output is correct
4 Correct 656 ms 120056 KB Output is correct
5 Correct 1324 ms 143720 KB Output is correct
6 Correct 1321 ms 143512 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 94328 KB Output is correct
2 Correct 87 ms 94328 KB Output is correct
3 Correct 88 ms 94328 KB Output is correct
4 Correct 87 ms 94328 KB Output is correct
5 Correct 87 ms 94248 KB Output is correct
6 Correct 87 ms 94328 KB Output is correct
7 Correct 87 ms 94328 KB Output is correct
8 Correct 87 ms 94328 KB Output is correct
9 Correct 87 ms 94328 KB Output is correct
10 Correct 88 ms 94328 KB Output is correct
11 Correct 87 ms 94328 KB Output is correct
12 Correct 87 ms 94328 KB Output is correct
13 Correct 87 ms 94312 KB Output is correct
14 Correct 87 ms 94456 KB Output is correct
15 Correct 87 ms 94328 KB Output is correct
16 Correct 87 ms 94328 KB Output is correct
17 Incorrect 87 ms 94412 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 94328 KB Output is correct
2 Correct 87 ms 94328 KB Output is correct
3 Correct 88 ms 94328 KB Output is correct
4 Correct 87 ms 94328 KB Output is correct
5 Correct 87 ms 94248 KB Output is correct
6 Correct 87 ms 94328 KB Output is correct
7 Correct 87 ms 94328 KB Output is correct
8 Correct 87 ms 94328 KB Output is correct
9 Correct 87 ms 94328 KB Output is correct
10 Correct 88 ms 94328 KB Output is correct
11 Correct 600 ms 141404 KB Output is correct
12 Correct 519 ms 138052 KB Output is correct
13 Correct 1334 ms 143884 KB Output is correct
14 Correct 656 ms 120056 KB Output is correct
15 Correct 1324 ms 143720 KB Output is correct
16 Correct 1321 ms 143512 KB Output is correct
17 Correct 87 ms 94328 KB Output is correct
18 Correct 87 ms 94328 KB Output is correct
19 Correct 87 ms 94312 KB Output is correct
20 Correct 87 ms 94456 KB Output is correct
21 Correct 87 ms 94328 KB Output is correct
22 Correct 87 ms 94328 KB Output is correct
23 Incorrect 87 ms 94412 KB Output isn't correct
24 Halted 0 ms 0 KB -