oj.uz

Submission #446002

# Submission time Handle Problem Language Result Execution time Memory
446002 2021-07-20T12:07:09 Z sinamhdv Mousetrap (CEOI17_mousetrap) C++11
100 / 100
 1112 ms 209420 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 1000100;

int n, t, m;
vector<int> adj[MAXN];
int dp[MAXN];
int par[MAXN];
int prv[MAXN], nxt[MAXN];
vector<int> path;
vector<int> dpvec[MAXN];

void dfs1(int v)
{
	for (int u : adj[v]) if (u != par[v]) par[u] = v, dfs1(u);
}

void dfs2(int v)
{
	vector<int> vec;
	for (int u : adj[v]) if (u != par[v] && u != prv[v] && u != nxt[v]) dfs2(u), vec.pb(dp[u]);
	sort(all(vec), greater<int>());
	dp[v] = vec.size() + ((int)vec.size() >= 2 ? vec[1] : 0);
}

bool check(int x)
{
	int blk = 0;
	FOR(i, 0, (int)path.size())
	{
		int v = path[i];
		int cur = 0;
		for (int u : dpvec[v]) if (blk + u > x) cur++;
		blk += cur;
		if (blk > i + 1) return false;
	}
	return blk <= x;
}

int32_t main(void)
{
	fast_io;
	cin >> n >> t >> m;
	if (m == t) return cout << "0\n", 0;
	FOR(i, 0, n - 1)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	dfs1(m);
	int v = t;
	while (v != m)
	{
		nxt[par[v]] = v;
		prv[v] = par[v];
		path.pb(v);
		v = par[v];
	}
	path.pb(m);
	reverse(all(path));
	path.pop_back();

	for (int u : path) dfs2(u);
	dbgr(dp + 1, dp + n + 1);

	int sm = 0;
	for (int i = (int)path.size() - 1; i >= 0; i--)
	{
		int v = path[i];
		for (int u : adj[v]) if (v != prv[u] && v != nxt[u]) dpvec[v].pb(dp[u]);
		sm += dpvec[v].size();
		FOR(j, 0, (int)dpvec[v].size()) dpvec[v][j] += sm;
	}

	int l = -1, r = 3 * n + 10;
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		if (check(mid)) r = mid;
		else l = mid;
	}

	cout << r << endl;

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47292 KB Output is correct
2 Correct 26 ms 47204 KB Output is correct
3 Correct 25 ms 47300 KB Output is correct
4 Correct 26 ms 47268 KB Output is correct
5 Correct 26 ms 47216 KB Output is correct
6 Correct 25 ms 47308 KB Output is correct
7 Correct 26 ms 47308 KB Output is correct
8 Correct 25 ms 47304 KB Output is correct
9 Correct 27 ms 47320 KB Output is correct
10 Correct 28 ms 47232 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 89416 KB Output is correct
2 Correct 396 ms 85608 KB Output is correct
3 Correct 1032 ms 90520 KB Output is correct
4 Correct 492 ms 69376 KB Output is correct
5 Correct 1099 ms 90612 KB Output is correct
6 Correct 1097 ms 90668 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47292 KB Output is correct
2 Correct 26 ms 47204 KB Output is correct
3 Correct 25 ms 47300 KB Output is correct
4 Correct 26 ms 47268 KB Output is correct
5 Correct 26 ms 47216 KB Output is correct
6 Correct 25 ms 47308 KB Output is correct
7 Correct 26 ms 47308 KB Output is correct
8 Correct 25 ms 47304 KB Output is correct
9 Correct 27 ms 47320 KB Output is correct
10 Correct 28 ms 47232 KB Output is correct
11 Correct 25 ms 47324 KB Output is correct
12 Correct 26 ms 47360 KB Output is correct
13 Correct 26 ms 47296 KB Output is correct
14 Correct 27 ms 47412 KB Output is correct
15 Correct 27 ms 47308 KB Output is correct
16 Correct 27 ms 47296 KB Output is correct
17 Correct 26 ms 47308 KB Output is correct
18 Correct 27 ms 47284 KB Output is correct
19 Correct 28 ms 47336 KB Output is correct
20 Correct 26 ms 47360 KB Output is correct
21 Correct 31 ms 47308 KB Output is correct
22 Correct 25 ms 47308 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47292 KB Output is correct
2 Correct 26 ms 47204 KB Output is correct
3 Correct 25 ms 47300 KB Output is correct
4 Correct 26 ms 47268 KB Output is correct
5 Correct 26 ms 47216 KB Output is correct
6 Correct 25 ms 47308 KB Output is correct
7 Correct 26 ms 47308 KB Output is correct
8 Correct 25 ms 47304 KB Output is correct
9 Correct 27 ms 47320 KB Output is correct
10 Correct 28 ms 47232 KB Output is correct
11 Correct 422 ms 89416 KB Output is correct
12 Correct 396 ms 85608 KB Output is correct
13 Correct 1032 ms 90520 KB Output is correct
14 Correct 492 ms 69376 KB Output is correct
15 Correct 1099 ms 90612 KB Output is correct
16 Correct 1097 ms 90668 KB Output is correct
17 Correct 25 ms 47324 KB Output is correct
18 Correct 26 ms 47360 KB Output is correct
19 Correct 26 ms 47296 KB Output is correct
20 Correct 27 ms 47412 KB Output is correct
21 Correct 27 ms 47308 KB Output is correct
22 Correct 27 ms 47296 KB Output is correct
23 Correct 26 ms 47308 KB Output is correct
24 Correct 27 ms 47284 KB Output is correct
25 Correct 28 ms 47336 KB Output is correct
26 Correct 26 ms 47360 KB Output is correct
27 Correct 31 ms 47308 KB Output is correct
28 Correct 25 ms 47308 KB Output is correct
29 Correct 26 ms 47292 KB Output is correct
30 Correct 428 ms 99812 KB Output is correct
31 Correct 410 ms 99852 KB Output is correct
32 Correct 448 ms 142972 KB Output is correct
33 Correct 464 ms 209420 KB Output is correct
34 Correct 1112 ms 100804 KB Output is correct
35 Correct 1111 ms 100912 KB Output is correct
36 Correct 1102 ms 107896 KB Output is correct
37 Correct 1101 ms 107896 KB Output is correct
38 Correct 853 ms 109880 KB Output is correct
39 Correct 888 ms 109748 KB Output is correct
40 Correct 819 ms 109792 KB Output is correct