oj.uz

Submission #137010

# Submission time Handle Problem Language Result Execution time Memory
137010 2019-07-26T22:16:12 Z thebes Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 1671 ms 108728 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 1e6+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){
    vector<int> vec;
    for(auto v : adj[n]){
        if(v==pp) continue;
        solve(v, n);
        vec.push_back(dp[v]);
    }
    sort(vec.begin(),vec.end(),[](int i,int j){return i>j;});
    if(vec.size()>=2) dp[n]=vec[1];
    dp[n]=max(dp[n],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;
    }
    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();
    }
    printf("%d\n",q.top());
    return 0;
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:44: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:45: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 44 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Runtime error 106 ms 95480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 107536 KB Output is correct
2 Correct 508 ms 101624 KB Output is correct
3 Correct 1416 ms 108588 KB Output is correct
4 Correct 643 ms 77944 KB Output is correct
5 Correct 1671 ms 108728 KB Output is correct
6 Correct 1568 ms 108608 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Runtime error 106 ms 95480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Runtime error 106 ms 95480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -