oj.uz

Submission #137013

# Submission time Handle Problem Language Result Execution time Memory
137013 2019-07-26T22:22:16 Z thebes Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 1723 ms 142672 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], ans, u[MN], d[MN];
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=n;i>=1;i--){
        for(auto v : w[i]) q.push(v);
        if(q.size()) q.pop();
    }
    if(q.empty()) printf("%d\n",cost[s]);
    else printf("%d\n",max(cost[s],q.top()));
    return 0;
}

Compilation message

mousetrap.cpp: In function 'int main()':
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 101 ms 94328 KB Output is correct
2 Correct 97 ms 94328 KB Output is correct
3 Correct 95 ms 94352 KB Output is correct
4 Correct 98 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 101 ms 94332 KB Output is correct
7 Correct 91 ms 94408 KB Output is correct
8 Correct 93 ms 94328 KB Output is correct
9 Correct 106 ms 94328 KB Output is correct
10 Correct 97 ms 94208 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 141456 KB Output is correct
2 Correct 558 ms 136696 KB Output is correct
3 Correct 1723 ms 142568 KB Output is correct
4 Correct 685 ms 118272 KB Output is correct
5 Correct 1606 ms 142672 KB Output is correct
6 Correct 1619 ms 142404 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 94328 KB Output is correct
2 Correct 97 ms 94328 KB Output is correct
3 Correct 95 ms 94352 KB Output is correct
4 Correct 98 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 101 ms 94332 KB Output is correct
7 Correct 91 ms 94408 KB Output is correct
8 Correct 93 ms 94328 KB Output is correct
9 Correct 106 ms 94328 KB Output is correct
10 Correct 97 ms 94208 KB Output is correct
11 Correct 88 ms 94244 KB Output is correct
12 Correct 89 ms 94300 KB Output is correct
13 Correct 89 ms 94328 KB Output is correct
14 Correct 89 ms 94376 KB Output is correct
15 Correct 89 ms 94328 KB Output is correct
16 Correct 87 ms 94344 KB Output is correct
17 Incorrect 94 ms 94456 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 94328 KB Output is correct
2 Correct 97 ms 94328 KB Output is correct
3 Correct 95 ms 94352 KB Output is correct
4 Correct 98 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 101 ms 94332 KB Output is correct
7 Correct 91 ms 94408 KB Output is correct
8 Correct 93 ms 94328 KB Output is correct
9 Correct 106 ms 94328 KB Output is correct
10 Correct 97 ms 94208 KB Output is correct
11 Correct 552 ms 141456 KB Output is correct
12 Correct 558 ms 136696 KB Output is correct
13 Correct 1723 ms 142568 KB Output is correct
14 Correct 685 ms 118272 KB Output is correct
15 Correct 1606 ms 142672 KB Output is correct
16 Correct 1619 ms 142404 KB Output is correct
17 Correct 88 ms 94244 KB Output is correct
18 Correct 89 ms 94300 KB Output is correct
19 Correct 89 ms 94328 KB Output is correct
20 Correct 89 ms 94376 KB Output is correct
21 Correct 89 ms 94328 KB Output is correct
22 Correct 87 ms 94344 KB Output is correct
23 Incorrect 94 ms 94456 KB Output isn't correct
24 Halted 0 ms 0 KB -