oj.uz

Submission #938380

# Submission time Handle Problem Language Result Execution time Memory
938380 2024-03-05T05:26:08 Z vjudge1 Mousetrap (CEOI17_mousetrap) C++17
0 / 100
 52 ms 16308 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <int> g[N];
int d[N],bl[N],par[N],par2[N];
void dfs(int v,int p){
    par[v]=p;
    for(auto to : g[v]){
        if(to!=p)dfs(to,v);
    }
    d[p]=max(d[p],d[v]+1);
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n,t,s;
    cin>>n>>t>>s;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(t,0);
    int ans=0;
    while(s!=t){
        int ind=-1,mx=-1,pos=0,cnt=0;
        for(auto to : g[s]){
            if(to!=par[s] && to!=par2[s]){
                cnt++;
                if(d[to]>mx){
                    mx=d[to];
                    ind=pos;
                }
            }
            pos++;
        }
        if(ind!=-1){
            ans++;cnt--;
        }
        pos=0;
        mx=-1;
        for(auto to : g[s]){
            if(to!=par[s] && to!=par2[s]){
                if(d[to]>mx && pos!=ind){
                    mx=d[to];
                }
            }
            pos++;
        }
        if(mx!=-1){
            if(mx>0)ans++;
            ans++;
            cnt--;
        }
        ans+=cnt;
        par2[par[s]]=s;
        s=par[s];
    }
    cout<<ans<<"\n";
}
/*

*/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 2 ms 5552 KB Output is correct
5 Incorrect 1 ms 5724 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 16308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 2 ms 5552 KB Output is correct
5 Incorrect 1 ms 5724 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 2 ms 5552 KB Output is correct
5 Incorrect 1 ms 5724 KB Output isn't correct
6 Halted 0 ms 0 KB -