oj.uz

Submission #571717

# Submission time Handle Problem Language Result Execution time Memory
571717 2022-06-02T15:18:32 Z BackNoob Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 864 ms 153420 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1) 
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 1e6 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 200;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

int n;
int t;
int m;
int deg[mxN];
int dp[mxN];
int par[mxN];
bool spec[mxN];
vector<int> adj[mxN];
vector<int> path;

void dfs(int u, int p)
{
	for(int v : adj[u]) {
		if(v == p) continue;
		par[v] = u;
		dfs(v, u);
	}
}

void calcdp(int u, int p)
{
	pair<int, int> best = {0, 0};
	for(int v : adj[u]) {
		if(v == p) continue;
		deg[u]++;
		calcdp(v, u);

		int tmp = best.fi;
		if(maximize(best.fi, dp[v]) == true) best.se = tmp;
		else maximize(best.se, dp[v]);
	}

	dp[u] = best.se + deg[u];
}

bool ok(int x)
{
	int sumdeg = 0;
	for(auto it : path) sumdeg += deg[it];

	if(sumdeg > x) return false;

	int cur = 0;
	int need = 0;
	for(auto u : path) {
		++cur;
		int re = 0;
		for(int v : adj[u]) {
			if(spec[v] == true) continue;
			re += (dp[v] + sumdeg) <= x;
			need += (dp[v] + sumdeg) > x;
		}
		sumdeg -= re;

		if(need > cur) return false;
	}
	return true;
}

void solve()
{	
	cin >> n >> t >> m;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	par[m] = 0;
	dfs(m, -1);

	int pos = t;
	while(pos != 0) {
		if(pos != t) path.pb(pos);
		pos = par[pos];	
	}

	reverse(all(path));
	spec[t] = true;
	for(auto it : path) spec[it] = true;

	for(auto u : path) {
		for(int v : adj[u]) {
			if(spec[v] == false) {
				calcdp(v, u);
				deg[u]++;
			}
		}
	}

	// cout << dp[6] << ' ' << dp[7] << ' ' << dp[3] << endl;

	int lo = 0, hi = inf;
	while(lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		if(ok(mid) == true) hi = mid;
		else lo = mid;
	}
	if(ok(lo)) cout << lo;
	else cout << hi;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".in" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
	

    int tc = 1;
    // cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 15 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23812 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23824 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 14 ms 23820 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 65984 KB Output is correct
2 Correct 259 ms 61996 KB Output is correct
3 Correct 793 ms 69160 KB Output is correct
4 Correct 352 ms 47000 KB Output is correct
5 Correct 744 ms 69116 KB Output is correct
6 Correct 771 ms 69196 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 15 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23812 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23824 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 14 ms 23820 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23892 KB Output is correct
14 Correct 13 ms 23800 KB Output is correct
15 Correct 13 ms 23892 KB Output is correct
16 Correct 13 ms 23892 KB Output is correct
17 Correct 14 ms 23784 KB Output is correct
18 Correct 13 ms 23892 KB Output is correct
19 Correct 15 ms 23892 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 13 ms 23780 KB Output is correct
22 Correct 12 ms 23860 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 15 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23812 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23824 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 14 ms 23820 KB Output is correct
11 Correct 278 ms 65984 KB Output is correct
12 Correct 259 ms 61996 KB Output is correct
13 Correct 793 ms 69160 KB Output is correct
14 Correct 352 ms 47000 KB Output is correct
15 Correct 744 ms 69116 KB Output is correct
16 Correct 771 ms 69196 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 12 ms 23764 KB Output is correct
19 Correct 12 ms 23892 KB Output is correct
20 Correct 13 ms 23800 KB Output is correct
21 Correct 13 ms 23892 KB Output is correct
22 Correct 13 ms 23892 KB Output is correct
23 Correct 14 ms 23784 KB Output is correct
24 Correct 13 ms 23892 KB Output is correct
25 Correct 15 ms 23892 KB Output is correct
26 Correct 12 ms 23764 KB Output is correct
27 Correct 13 ms 23780 KB Output is correct
28 Correct 12 ms 23860 KB Output is correct
29 Correct 12 ms 23764 KB Output is correct
30 Correct 306 ms 73112 KB Output is correct
31 Correct 283 ms 73312 KB Output is correct
32 Correct 397 ms 96672 KB Output is correct
33 Correct 328 ms 153420 KB Output is correct
34 Correct 782 ms 76240 KB Output is correct
35 Correct 771 ms 76244 KB Output is correct
36 Correct 864 ms 78788 KB Output is correct
37 Correct 846 ms 78864 KB Output is correct
38 Correct 569 ms 78356 KB Output is correct
39 Correct 580 ms 78440 KB Output is correct
40 Correct 553 ms 78400 KB Output is correct