Submission #938304

#	Time	Username	Problem	Language	Result	Execution time	Memory
938304		vjudge1	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	51 ms	16232 KiB

mousetrap

#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;
        int mn=1e7;
        for(auto to : g[s]){
            if(to!=par[s] && to!=par2[s]){
                if(d[to]<mn && pos!=ind){
                    mn=d[to];
                }
            }
            pos++;
        }
        if(mn!=1e7){
            if(mn>0)ans++;
            ans++;
            cnt--;
        }
        ans+=cnt;
        par2[par[s]]=s;
        s=par[s];
    }
    cout<<ans<<"\n";
}
/*

*/

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35