Submission #1196040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196040		loom	Mousetrap (CEOI17_mousetrap)	C++20	100 / 100	453 ms	243092 KiB

mousetrap

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

const int N = 1e6+1;
vector<int> g[N];
int dp[N], pr[N];
int t;

void dfs(int v, int p, int wt){
   vector<int> w;
   for(int ch : g[v]){
      if(ch == p) continue;

      pr[ch] = v;
      dfs(ch, v, (v == t ? 0 : wt + g[v].size()-2));
      w.push_back(dp[ch]);
   }
   sort(w.rbegin(), w.rend());

   dp[v] = (w.size() >= 2 ? w[1]+1 : wt);
   if(w.size() == 1) dp[v]++;
}

inline void solve(){
   int n, m;
   cin>>n>>t>>m;
   for(int i=1; i<n; i++){
      int a, b;
      cin>>a>>b;
      g[a].push_back(b);
      g[b].push_back(a);
   }

   dfs(t, 0, 0);

   int lo = 0, hi = 1e7;
   while(lo < hi){
      int wt = (lo+hi)/2;

      int v = m, pv = 0, pb = 0, tb = 0, d = 1, tf = 1;
      while(v != t){
         for(int ch : g[v]){
            if(ch == pr[v] or ch == pv or dp[ch]+1 + pb - (v != m) <= wt) continue;
            if(tb >= d) tf = 0;
            tb++;
         }

         pb = tb;
         pv = v;
         v = pr[v];
         d++;
      }

      if(tf and tb <= wt) hi = wt;
      else lo = wt+1;
   }

   cout<<lo;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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