Submission #1195779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195779		loom	Mousetrap (CEOI17_mousetrap)	C++20	45 / 100	703 ms	78716 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, b = 0, d = 1, tf = 1;
      while(v != t){
         for(int ch : g[v]){
            if(ch == pr[v] or ch == pv or dp[ch] < wt) continue;
            if(b >= d) tf = 0;
            b++; 
         }

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

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

   int v = m, pv = 0, b = 0;
   while(v != t){
      for(int ch : g[v]){
         if(ch != pr[v] and ch != pv and dp[ch] == lo-1){
            cout<<b+lo - (v != m ? 1 : 0);
            return;
         }
      }

      for(int ch : g[v]) if(ch != pr[v] and ch != pv and dp[ch] >= lo) b++;
      
      pv = v;
      v = pr[v];
   }   

   cout<<b;
}

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: 0 / 20
• Subtask 4: 0 / 35