oj.uz

Submission #570070

# Submission time Handle Problem Language Result Execution time Memory
570070 2022-05-28T14:02:33 Z jesus_coconut Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 789 ms 69440 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 68436 KB Output is correct
2 Correct 289 ms 61516 KB Output is correct
3 Correct 789 ms 69440 KB Output is correct
4 Correct 332 ms 34680 KB Output is correct
5 Correct 777 ms 69324 KB Output is correct
6 Correct 727 ms 69356 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -