oj.uz

Submission #118340

# Submission time Handle Problem Language Result Execution time Memory
118340 2019-06-18T16:53:10 Z teomrn Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 1229 ms 81308 KB 
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1000010;
vector <int> adia[NMAX];
int cost[NMAX];
int tata[NMAX];
int h[NMAX];
int nr_op;

void dfs(int nod, int t)
{
	if (t)
		adia[nod].erase(find(adia[nod].begin(), adia[nod].end(), t));
	tata[nod] = t;
	h[nod] = 1 + h[t];

	for (auto i : adia[nod])
		dfs(i, nod);
}

void calc_cost(int nod)
{
	for (auto i : adia[nod])
		calc_cost(i);

	int max1 = 0, max2 = 0;
	for (auto i : adia[nod]) {
		if (cost[i] > max1)
			max2 = max1, max1 = cost[i];
		else if (cost[i] > max2)
			max2 = cost[i];
	}

	cost[nod] = adia[nod].size() + max2;
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, root, x;
	cin >> n >> root >> x;

	if (root == x) {
		cout << "0\n";
		return 0;
	}

	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adia[a].push_back(b);
		adia[b].push_back(a);
	}

	dfs(root, 0);
	calc_cost(x);

	int ans = cost[x];
	x = tata[x];

	while (x != root) {
		ans += adia[x].size() - 1;
		x = tata[x];
	}

	cout << ans << '\n';

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 21 ms 23808 KB Output is correct
6 Correct 22 ms 23808 KB Output is correct
7 Correct 21 ms 23808 KB Output is correct
8 Correct 21 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 21 ms 23808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 80196 KB Output is correct
2 Correct 339 ms 74732 KB Output is correct
3 Correct 1150 ms 81248 KB Output is correct
4 Correct 544 ms 52376 KB Output is correct
5 Correct 1171 ms 81308 KB Output is correct
6 Correct 1229 ms 81192 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 21 ms 23808 KB Output is correct
6 Correct 22 ms 23808 KB Output is correct
7 Correct 21 ms 23808 KB Output is correct
8 Correct 21 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 21 ms 23808 KB Output is correct
11 Incorrect 23 ms 23808 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 21 ms 23808 KB Output is correct
5 Correct 21 ms 23808 KB Output is correct
6 Correct 22 ms 23808 KB Output is correct
7 Correct 21 ms 23808 KB Output is correct
8 Correct 21 ms 23808 KB Output is correct
9 Correct 21 ms 23808 KB Output is correct
10 Correct 21 ms 23808 KB Output is correct
11 Correct 387 ms 80196 KB Output is correct
12 Correct 339 ms 74732 KB Output is correct
13 Correct 1150 ms 81248 KB Output is correct
14 Correct 544 ms 52376 KB Output is correct
15 Correct 1171 ms 81308 KB Output is correct
16 Correct 1229 ms 81192 KB Output is correct
17 Incorrect 23 ms 23808 KB Output isn't correct
18 Halted 0 ms 0 KB -