Submission #563706

#	Time	Username	Problem	Language	Result	Execution time	Memory
563706		hohohaha	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	600 ms	60168 KiB

mousetrap

#include<bits/stdc++.h>
using namespace std;

#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define em emplace
#define sp ' '
#define endl '\n'
//#define int long long

#define ld long double

const int maxn = 1e6 + 5; 

int n; 
vi g[maxn]; 
int m, t;
int dp[maxn]; 

void dfs_solve(int u, int p) { 	
	if(g[u].size() == 1) {
		dp[u] = 0; 
	}
	else {
    	int mx = 0, mx2 = 0; 
    	for(int v: g[u]) { 
    		if(v == p) continue; 
    		dfs_solve(v, u); 
    		if(dp[v] > mx) { 
    			mx2 = mx; 
    			mx = dp[v]; 
    		}
    		else if(dp[v] > mx2) { 
    			mx2 = dp[v]; 
    		}
    	}
    	dp[u] = g[u].size() + mx2 - 1; 
	}
}

signed main() { 
//	freopen("oneway.inp", "r", stdin); 
//	freopen("oneway.out", "w", stdout); 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	
	cin >> n >> t >> m; 
	fori(i, 1, n - 1) { 
	 	int u, v; cin >> u >> v; 
	 	g[u].eb(v); 
	 	g[v].eb(u); 
	 }
	if(count(begin(g[t]), end(g[t]), m)) {
		 dfs_solve(m, t); 
		cout << dp[m];  
	}
}

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