oj.uz

Submission #541906

# Submission time Handle Problem Language Result Execution time Memory
541906 2022-03-24T18:54:25 Z Asymmetry Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 399 ms 62896 KB 
//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

const int N = 1001000;
int n, a, b, m, q;
int par[N];
int son[N];
int cost[N];
int blk[N];
int dp[N]; // ile żeby uwięzić i wyprowadzić do ojca
vector<int> v[N];

void dfs_dp(int x) {
	vector<int> war = {0, 0};
	for (int i : v[x]) {
		if (i == par[x]) {
			continue;
		}
		par[i] = x;
		dfs_dp(i);
		war.push_back(dp[i]);
	}
	nth_element(war.begin(), war.begin() + 1, war.end(), [&](int a, int b) {
		return a > b;
	});
	dp[x] = war[1] + war.size() - 2;
}

bool check(int wyn) {
	int x = m, nad = 1, usd = 0;
	while (x != q) {
		int ile = 0;
		for (int i : v[x]) {
			if (i != par[x] && i != son[x]) {
				if (dp[i] + blk[x] + usd > wyn) {
					++ile;
				}
			}
		}
		if (ile > nad) {
			return false;
		}
		nad -= ile;
		usd += ile;
		x = par[x];
		++nad;
	}
	return usd <= wyn;
}

int main() {
	scanf("%d%d%d", &n, &q, &m);
	for (int i = 1; i < n; ++i) {
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs_dp(q);
	int x = m;
	while (x != q) {
		son[par[x]] = x;
		x = par[x];
	}
	while (x != m) {
		x = son[x];
		blk[x] = blk[par[x]];
		for (int i : v[x]) {
			blk[x] += (i != par[x]) && (i != son[x]);
		}
	}
	int bp = -1, bk = min(n, 30), bs;
	while (bk - bp > 1) {
		bs = (bp + bk) / 2;
		if (check(bs)) {
			bk = bs;
		}
		else {
			bp = bs;
		}
	}
	printf("%d\n", bk);
	return 0;
}

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d%d%d", &n, &q, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23740 KB Output is correct
3 Correct 15 ms 23732 KB Output is correct
4 Correct 12 ms 23768 KB Output is correct
5 Correct 12 ms 23844 KB Output is correct
6 Correct 13 ms 23744 KB Output is correct
7 Correct 12 ms 23816 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 13 ms 23748 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23740 KB Output is correct
3 Correct 15 ms 23732 KB Output is correct
4 Correct 12 ms 23768 KB Output is correct
5 Correct 12 ms 23844 KB Output is correct
6 Correct 13 ms 23744 KB Output is correct
7 Correct 12 ms 23816 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 13 ms 23748 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 12 ms 23880 KB Output is correct
13 Correct 12 ms 23864 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23952 KB Output is correct
16 Incorrect 13 ms 23892 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23740 KB Output is correct
3 Correct 15 ms 23732 KB Output is correct
4 Correct 12 ms 23768 KB Output is correct
5 Correct 12 ms 23844 KB Output is correct
6 Correct 13 ms 23744 KB Output is correct
7 Correct 12 ms 23816 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 13 ms 23748 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Incorrect 399 ms 62896 KB Output isn't correct
12 Halted 0 ms 0 KB -