oj.uz

Submission #570101

# Submission time Handle Problem Language Result Execution time Memory
570101 2022-05-28T14:33:18 Z jesus_coconut Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 821 ms 60188 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define pb push_back
#define all(a) begin(a), end(a)
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;

using oset = tree<pair<int, int>, null_type, greater<>, rb_tree_tag, tree_order_statistics_node_update>;

int const N = 1000005;

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

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

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

int sc = 0;
int ans = 0;
oset s;
int cnt = 0;
int dfs2(int ver, int par) {
	if (ver != t) sc += adj[ver].size() - 1;
	if (ver == m) {
		for (auto u : adj[ver]) if (u != par) {
			s.insert({val[u] + sc, cnt++});
		}
		if (cnt >= 2) {	
			ans = max(ans, s.find_by_order(1)->F);
		}
		if (ver != t) sc -= adj[ver].size() - 1;
		return 2;
	} else {
		if (ver != t) sc--;
		for (auto u : adj[ver]) if (u != par) {
			int x = dfs2(u, ver);
			if (x) {
				for (auto y : adj[ver]) if (y != par && y != u) {
					s.insert({val[y] + sc, cnt++});
				}
				if (cnt > x) {
					ans = max(ans, s.find_by_order(x)->F);
				}
				if (ver != t) {
					sc -= adj[ver].size() - 1;
					sc++;
				}
				return x + 1;
			}
		}
		if (ver != t) {
			sc -= adj[ver].size() - 1;
			sc++;
		}
		return 0;
	}
}

void solve() {
	memset(val, -1, sizeof val);
	dfs(0, -1);
	dfs2(t, -1);
	cout << ans << '\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 Incorrect 3 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 58928 KB Output is correct
2 Correct 285 ms 53464 KB Output is correct
3 Correct 797 ms 60084 KB Output is correct
4 Correct 355 ms 32204 KB Output is correct
5 Correct 821 ms 60124 KB Output is correct
6 Correct 787 ms 60188 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -