oj.uz

Submission #45099

# Submission time Handle Problem Language Result Execution time Memory
45099 2018-04-11T09:23:18 Z qoo2p5 Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 1214 ms 61492 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 (k <= cnt) {
		cnt -= k;
		cur = k;
	} 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 21 ms 23800 KB Output is correct
2 Correct 20 ms 24040 KB Output is correct
3 Correct 21 ms 24040 KB Output is correct
4 Correct 21 ms 24040 KB Output is correct
5 Correct 21 ms 24040 KB Output is correct
6 Correct 23 ms 24076 KB Output is correct
7 Correct 21 ms 24088 KB Output is correct
8 Correct 22 ms 24088 KB Output is correct
9 Correct 25 ms 24088 KB Output is correct
10 Correct 25 ms 24088 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 59816 KB Output is correct
2 Correct 573 ms 59816 KB Output is correct
3 Correct 1200 ms 61392 KB Output is correct
4 Correct 586 ms 61392 KB Output is correct
5 Correct 1171 ms 61408 KB Output is correct
6 Correct 1214 ms 61492 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 20 ms 24040 KB Output is correct
3 Correct 21 ms 24040 KB Output is correct
4 Correct 21 ms 24040 KB Output is correct
5 Correct 21 ms 24040 KB Output is correct
6 Correct 23 ms 24076 KB Output is correct
7 Correct 21 ms 24088 KB Output is correct
8 Correct 22 ms 24088 KB Output is correct
9 Correct 25 ms 24088 KB Output is correct
10 Correct 25 ms 24088 KB Output is correct
11 Incorrect 21 ms 61492 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 20 ms 24040 KB Output is correct
3 Correct 21 ms 24040 KB Output is correct
4 Correct 21 ms 24040 KB Output is correct
5 Correct 21 ms 24040 KB Output is correct
6 Correct 23 ms 24076 KB Output is correct
7 Correct 21 ms 24088 KB Output is correct
8 Correct 22 ms 24088 KB Output is correct
9 Correct 25 ms 24088 KB Output is correct
10 Correct 25 ms 24088 KB Output is correct
11 Correct 514 ms 59816 KB Output is correct
12 Correct 573 ms 59816 KB Output is correct
13 Correct 1200 ms 61392 KB Output is correct
14 Correct 586 ms 61392 KB Output is correct
15 Correct 1171 ms 61408 KB Output is correct
16 Correct 1214 ms 61492 KB Output is correct
17 Incorrect 21 ms 61492 KB Output isn't correct
18 Halted 0 ms 0 KB -