oj.uz

Submission #118343

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

const int NMAX = 1000010;
vector <int> adia[NMAX];
int cost[NMAX];
int tata[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;

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

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

	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 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 23 ms 23788 KB Output is correct
4 Correct 23 ms 23808 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 23 ms 23808 KB Output is correct
7 Correct 23 ms 23808 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 23 ms 23808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 63128 KB Output is correct
2 Correct 348 ms 59256 KB Output is correct
3 Correct 966 ms 64240 KB Output is correct
4 Correct 448 ms 44024 KB Output is correct
5 Correct 987 ms 64360 KB Output is correct
6 Correct 1014 ms 64376 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 23 ms 23788 KB Output is correct
4 Correct 23 ms 23808 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 23 ms 23808 KB Output is correct
7 Correct 23 ms 23808 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 23 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 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 23 ms 23788 KB Output is correct
4 Correct 23 ms 23808 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 23 ms 23808 KB Output is correct
7 Correct 23 ms 23808 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 23 ms 23808 KB Output is correct
10 Correct 23 ms 23808 KB Output is correct
11 Correct 378 ms 63128 KB Output is correct
12 Correct 348 ms 59256 KB Output is correct
13 Correct 966 ms 64240 KB Output is correct
14 Correct 448 ms 44024 KB Output is correct
15 Correct 987 ms 64360 KB Output is correct
16 Correct 1014 ms 64376 KB Output is correct
17 Incorrect 23 ms 23808 KB Output isn't correct
18 Halted 0 ms 0 KB -