Submission #1195640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195640		loom	Mousetrap (CEOI17_mousetrap)	C++20	25 / 100	420 ms	70912 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];

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

      dfs(ch, v, wt + g[ch].size()-1);
      w.push_back(dp[ch]);
   }
   sort(w.rbegin(), w.rend());

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

inline void solve(){
   int n, t, 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);
   cout<<dp[m];
}

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