oj.uz

Submission #103720

# Submission time Handle Problem Language Result Execution time Memory
103720 2019-04-02T08:56:13 Z E869120 Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 2513 ms 246108 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

const int MAX_N = (1 << 20);

int N, A, B, E[MAX_N], F[MAX_N], dist[MAX_N], dp[MAX_N][22], val[MAX_N], pl[MAX_N]; bool used[MAX_N];
vector<int>X[MAX_N], Z[MAX_N], lis[MAX_N];

void dfs1(int pos, int dep) {
	used[pos] = true; dist[pos] = dep;
	for (int i = 0; i < X[pos].size(); i++) {
		if (used[X[pos][i]] == true) continue;
		dp[X[pos][i]][0] = pos;
		dfs1(X[pos][i], dep + 1);
	}
}

int prevs(int pos, int x) {
	for (int i = 21; i >= 0; i--) {
		if (x >= (1 << i)) { pos = dp[pos][i]; x -= (1 << i); }
	}
	return pos;
}

int lca(int u, int v) {
	if (dist[u] > dist[v]) swap(u, v);
	v = prevs(v, dist[v] - dist[u]);
	if (u == v) return u;

	for (int i = 21; i >= 0; i--) {
		if (dp[u][i] != dp[v][i]) {
			u = dp[u][i];
			v = dp[v][i];
		}
	}
	return dp[u][0];
}

int ret[MAX_N], root = 0;

int dfs2(int pos) {
	used[pos] = true;
	int bonus = 0; if (pos == root) bonus = 1;
	if ((int)Z[pos].size() + bonus <= 1) {
		return 0;
	}
	if ((int)Z[pos].size() + bonus == 2) {
		return 1;
	}

	vector<int>vec;
	for (int i = 0; i < Z[pos].size(); i++) {
		if (used[Z[pos][i]] == true) continue;
		vec.push_back(dfs2(Z[pos][i]));
	}
	sort(vec.begin(), vec.end());

	int V = vec[vec.size() - 2];
	return V + vec.size();
}

int main() {
	scanf("%d%d%d", &N, &A, &B);
	for (int i = 1; i <= N - 1; i++) {
		scanf("%d%d", &E[i], &F[i]);
		X[E[i]].push_back(F[i]);
		X[F[i]].push_back(E[i]);
	}
	dfs1(B, 0);
	for (int i = 0; i < 21; i++) {
		for (int j = 1; j <= N; j++) dp[j][i + 1] = dp[dp[j][i]][i];
	}

	for (int i = 1; i <= N; i++) {
		int v = lca(A, i);
		val[i] = dist[v];
		if (v == i) pl[dist[v]] = i;
		else lis[dist[v]].push_back(i);
	}

	int FinalAns = 0;

	for (int i = 1; i <= N; i++) used[i] = false;
	for (int i = 0; i < dist[A]; i++) {
		for (int j = 0; j < lis[i].size(); j++) {
			int u = lis[i][j], v = dp[u][0];
			Z[u].push_back(v);
			Z[v].push_back(u);
		}
		root = pl[i];
		int rem = dfs2(pl[i]);
		if (Z[pl[i]].size() == 1) rem = 1;
		if (Z[pl[i]].size() <= 0) rem = 0;

		FinalAns += rem;
	}
	cout << FinalAns << endl;
	return 0;
}

Compilation message

mousetrap.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
mousetrap.cpp: In function 'void dfs1(int, int)':
mousetrap.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int dfs2(int)':
mousetrap.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Z[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < lis[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
mousetrap.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &E[i], &F[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 74232 KB Output is correct
2 Correct 69 ms 74232 KB Output is correct
3 Correct 72 ms 74232 KB Output is correct
4 Correct 74 ms 74232 KB Output is correct
5 Incorrect 72 ms 74232 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 1259 ms 243772 KB Output is correct
2 Correct 1114 ms 226752 KB Output is correct
3 Correct 2513 ms 246108 KB Output is correct
4 Correct 1171 ms 160208 KB Output is correct
5 Correct 2477 ms 245840 KB Output is correct
6 Correct 2433 ms 245924 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 74232 KB Output is correct
2 Correct 69 ms 74232 KB Output is correct
3 Correct 72 ms 74232 KB Output is correct
4 Correct 74 ms 74232 KB Output is correct
5 Incorrect 72 ms 74232 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 74232 KB Output is correct
2 Correct 69 ms 74232 KB Output is correct
3 Correct 72 ms 74232 KB Output is correct
4 Correct 74 ms 74232 KB Output is correct
5 Incorrect 72 ms 74232 KB Output isn't correct
6 Halted 0 ms 0 KB -