Submission #563726

#	Time	Username	Problem	Language	Result	Execution time	Memory
563726		hohohaha	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	642 ms	60128 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;
bool in[maxn]; 
int dp[maxn]; 
int pref[maxn]; 
void mark(int u, int p, int des) { 
	if(u == des) { 
	 	in[u] = 1; 
	 	return; 
	 }
	for(int v: g[u]) { 
		if(v - p) { 
			mark(v, u, des);
			in[u] |= in[v]; 
		}
	}
}
			

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; 
	}
}

int dfs_solve_2(int u, int p) {
	int nxt = -1; 
	for(int v: g[u]) if(v - p and in[v]) nxt = v; 
	if(nxt == -1) return 0; 

	int temp = dfs_solve_2(nxt, u); 
	pref[u] = pref[nxt]; 
	
	int mx = 0, mx2 = 0; 
	for(int v: g[u]) { 
		if(!in[v]) { 
			pref[u]++;
			if(dp[v] > mx) { 
				mx2 = mx; 
				mx = dp[v]; 
			}
			else if(dp[v] > mx2) { 
				mx2 = dp[v]; 
			}
		}
	}
	
	//cout << mx2 << sp << pref[u] << endl;  
	
	return min(max(mx2 + pref[u], temp + 1), max(mx + pref[u], temp)); 
}

signed main() { 
	//freopen("mousetrap.inp", "r", stdin); 
//	freopen("mousetrap.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); 
	 }
	 
	mark(t, t, m); 
	
	fori(i, 1, n) { 
		if(in[i]) {
			//cout << i << sp;  
			for(int j: g[i]) {
				if(!in[j]) {
					dfs_solve(j, i); 
				}
			}
		}
	}
	cout << dfs_solve_2(m, m); 
}

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