oj.uz

Submission #535510

# Submission time Handle Problem Language Result Execution time Memory
535510 2022-03-10T12:13:31 Z Asymmetry Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 1051 ms 68068 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 stp[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;
}

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);
		++stp[a];
		++stp[b];
	}
	dfs_dp(q);
	int x = m;
	while (x != q) {
		son[par[x]] = x;
		x = par[x];
	}
	while (stp[m] == 1 && m != q) {
		--stp[par[m]];
		m = par[m];
	}
	cost[x] = 0;
	while (x != m) {
		x = son[x];
		blk[x] = blk[par[x]];
		vector<int> war = {0, 0};
		for (int i : v[x]) {
			if (i != par[x] && i != son[x]) {
				war.push_back(dp[i]);
				++blk[x];
			}
		}
		nth_element(war.begin(), war.begin() + 1, war.end(), [&](int a, int b) {
			return a > b;
		});
		cost[x] = max(war[1] + blk[x], cost[x]);
	}
	//~ for (int i = 1; i <= n; ++i) {
		//~ printf("%d: %d\n", i, dp[i]);
	//~ }
	printf("%d\n", cost[m]);
	return 0;
}

Compilation message

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23844 KB Output is correct
2 Correct 13 ms 23772 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23744 KB Output is correct
5 Incorrect 12 ms 23764 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 66772 KB Output is correct
2 Correct 336 ms 62504 KB Output is correct
3 Correct 1051 ms 68036 KB Output is correct
4 Correct 432 ms 46020 KB Output is correct
5 Correct 1026 ms 67976 KB Output is correct
6 Correct 949 ms 68068 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23844 KB Output is correct
2 Correct 13 ms 23772 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23744 KB Output is correct
5 Incorrect 12 ms 23764 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23844 KB Output is correct
2 Correct 13 ms 23772 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23744 KB Output is correct
5 Incorrect 12 ms 23764 KB Output isn't correct
6 Halted 0 ms 0 KB -