Submission #570070

#	Time	Username	Problem	Language	Result	Execution time	Memory
570070		jesus_coconut	Mousetrap (CEOI17_mousetrap)	C++17	25 / 100	789 ms	69440 KiB

mousetrap

#include <bits/stdc++.h>
#define pb push_back
#define all(a) begin(a), end(a)
using namespace std;

int const N = 1000005;

int n, t, m;
vector<vector<int>> adj;

int st = 0;
void load() {
	cin >> n >> t >> m;
	--t; --m;
	adj.resize(n);
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		--u; --v;
		adj[u].pb(v);
		adj[v].pb(u);
		
	}
	for (auto u : adj[t]) {
		if (u == m) {
			st = 2;
		}
	}
}


int dfs(int ver, int par) {
	int ans = adj[ver].size() - 1;
	vector<int> tmp;
	for (auto u : adj[ver]) if (u != par) {
		tmp.pb(dfs(u, ver));
	}
	sort(all(tmp), greater<>());
	if (size(tmp) >= 2) {
		ans += tmp[1];
	}
	return ans;
}

void solve() {
	assert(st == 2);
	cout << dfs(m, t) << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	load();
	solve();

	return 0;
}

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