oj.uz

Submission #45100

# Submission time Handle Problem Language Result Execution time Memory
45100 2018-04-11T09:28:29 Z qoo2p5 Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 1220 ms 61524 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = (int) 1e6 + 123;

int n, t, m;
vector<int> g[N];
int dp[N], out[N];
bool has[N];

void dfs(int v, int f = -1) {
	if (v == t) {
		has[v] = 1;
		return;
	}
	
	int pos = -1;
	int ptr = 0;
	for (int u : g[v]) {
		if (u == f) {
			pos = ptr;
			ptr++;
			continue;
		}
		dfs(u, v);
		has[v] |= has[u];
		ptr++;
	}
	if (pos != -1) {
		g[v].erase(g[v].begin() + pos);
	}
	
	vector<int> outs;
	for (int u : g[v]) {
		outs.pb(out[u]);
	}
	if (sz(outs) == 0) {
		out[v] = 0;
	} else if (sz(outs) == 1) {
		out[v] = 1;
	} else {
		sort(all(outs));
		int k = sz(outs);
		out[v] = outs[k - 2] + k;
	}
}

int solve(int v, int cnt) {
	if (v == t) {
		return 0;
	}
	
	assert(has[v]);
	int to = -1;
	vector<int> outs;
	for (int u : g[v]) {
		if (has[u]) {
			to = u;
		} else {
			outs.pb(out[u]);
		}
	}
	assert(to != -1);
	sort(all(outs));
	cnt++;
	int k = sz(outs);
	int cur;
	
	if (cnt >= INF) {
		return solve(to, cnt) + k;
	} else if (k <= cnt) {
		int res = k + solve(to, cnt - k);
		if (k > 0) {
			mini(res, k + outs[0] + solve(to, INF));
		}
		return res;
	} else {
		assert(k >= 2);
		cur = outs[k - 1 - cnt] + k;
		cnt = INF;
		return cur + solve(to, cnt);
	}
}

void run() {
	cin >> n >> t >> m;
	rep(i, 0, n - 1) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	
	dfs(m);
	cout << solve(m, 0) << "\n";
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 59688 KB Output is correct
2 Correct 463 ms 59688 KB Output is correct
3 Correct 1181 ms 61524 KB Output is correct
4 Correct 553 ms 61524 KB Output is correct
5 Correct 1220 ms 61524 KB Output is correct
6 Correct 1214 ms 61524 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 21 ms 23912 KB Output is correct
3 Correct 22 ms 23912 KB Output is correct
4 Correct 22 ms 23912 KB Output is correct
5 Correct 21 ms 23912 KB Output is correct
6 Correct 24 ms 24108 KB Output is correct
7 Correct 20 ms 24172 KB Output is correct
8 Correct 21 ms 24172 KB Output is correct
9 Correct 20 ms 24172 KB Output is correct
10 Correct 20 ms 24172 KB Output is correct
11 Correct 39 ms 61524 KB Output is correct
12 Correct 24 ms 61524 KB Output is correct
13 Correct 24 ms 61524 KB Output is correct
14 Correct 21 ms 61524 KB Output is correct
15 Correct 22 ms 61524 KB Output is correct
16 Correct 25 ms 61524 KB Output is correct
17 Incorrect 27 ms 61524 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 21 ms 23912 KB Output is correct
3 Correct 22 ms 23912 KB Output is correct
4 Correct 22 ms 23912 KB Output is correct
5 Correct 21 ms 23912 KB Output is correct
6 Correct 24 ms 24108 KB Output is correct
7 Correct 20 ms 24172 KB Output is correct
8 Correct 21 ms 24172 KB Output is correct
9 Correct 20 ms 24172 KB Output is correct
10 Correct 20 ms 24172 KB Output is correct
11 Correct 559 ms 59688 KB Output is correct
12 Correct 463 ms 59688 KB Output is correct
13 Correct 1181 ms 61524 KB Output is correct
14 Correct 553 ms 61524 KB Output is correct
15 Correct 1220 ms 61524 KB Output is correct
16 Correct 1214 ms 61524 KB Output is correct
17 Correct 39 ms 61524 KB Output is correct
18 Correct 24 ms 61524 KB Output is correct
19 Correct 24 ms 61524 KB Output is correct
20 Correct 21 ms 61524 KB Output is correct
21 Correct 22 ms 61524 KB Output is correct
22 Correct 25 ms 61524 KB Output is correct
23 Incorrect 27 ms 61524 KB Output isn't correct
24 Halted 0 ms 0 KB -