oj.uz

Submission #103729

# Submission time Handle Problem Language Result Execution time Memory
103729 2019-04-02T09:36:11 Z E869120 Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 2992 ms 245996 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, G = 2;

int dfs2(int pos) {
	used[pos] = true;
	int bonus = 0; if (pos == root) bonus = 1;
	if ((int)Z[pos].size() + bonus <= G) {
		return max(1, (int)Z[pos].size() + bonus) - 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 GG = 2; if (pos == root && G >= 2) GG = G;
	int V = vec[max(0, (int)vec.size() - GG)];
	if (vec.size() < GG && G >= 2) V = 0;
	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 Ans1 = 0, Ans2 = (1 << 30);

	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 B1 = (1 << 30), B2 = (1 << 30);
		// Ans1 -> Ans1
		for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
		G = 2; int Z1 = dfs2(pl[i]);
		B1 = min(B1, Ans1 + Z1);

		// Ans1 -> Ans2
		for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
		G = 1; int Z2 = dfs2(pl[i]);
		B2 = min(B2, Ans1 + Z2);

		// Ans2 -> Ans2
		for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
		G = 1000000; int Z3 = dfs2(pl[i]);
		B2 = min(B2, Ans2 + Z3);

		Ans1 = B1; Ans2 = B2;
	}
	cout << min(Ans1, Ans2) << 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:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Z[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
mousetrap.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (vec.size() < GG && G >= 2) V = 0;
      ~~~~~~~~~~~^~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < lis[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
mousetrap.cpp:96:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
   ^~~
mousetrap.cpp:96:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
                                         ^~~~
mousetrap.cpp:101:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
   ^~~
mousetrap.cpp:101:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
                                         ^~~~
mousetrap.cpp:106:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
   ^~~
mousetrap.cpp:106:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int j : lis[i]) used[j] = false; used[pl[i]] = false;
                                         ^~~~
mousetrap.cpp:65: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:67: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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 74232 KB Output is correct
2 Correct 72 ms 74232 KB Output is correct
3 Correct 76 ms 74232 KB Output is correct
4 Correct 75 ms 74252 KB Output is correct
5 Correct 80 ms 74232 KB Output is correct
6 Correct 73 ms 74232 KB Output is correct
7 Correct 73 ms 74232 KB Output is correct
8 Correct 74 ms 74232 KB Output is correct
9 Correct 73 ms 74232 KB Output is correct
10 Correct 77 ms 74360 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1368 ms 243808 KB Output is correct
2 Correct 1156 ms 226752 KB Output is correct
3 Correct 2992 ms 245964 KB Output is correct
4 Correct 1286 ms 160236 KB Output is correct
5 Correct 2676 ms 245996 KB Output is correct
6 Correct 2784 ms 245852 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 72 ms 74232 KB Output is correct
3 Correct 76 ms 74232 KB Output is correct
4 Correct 75 ms 74252 KB Output is correct
5 Correct 80 ms 74232 KB Output is correct
6 Correct 73 ms 74232 KB Output is correct
7 Correct 73 ms 74232 KB Output is correct
8 Correct 74 ms 74232 KB Output is correct
9 Correct 73 ms 74232 KB Output is correct
10 Correct 77 ms 74360 KB Output is correct
11 Correct 69 ms 74232 KB Output is correct
12 Correct 68 ms 74488 KB Output is correct
13 Correct 73 ms 74488 KB Output is correct
14 Correct 82 ms 74360 KB Output is correct
15 Correct 73 ms 74360 KB Output is correct
16 Correct 73 ms 74360 KB Output is correct
17 Incorrect 73 ms 74488 KB Output isn't correct
18 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 72 ms 74232 KB Output is correct
3 Correct 76 ms 74232 KB Output is correct
4 Correct 75 ms 74252 KB Output is correct
5 Correct 80 ms 74232 KB Output is correct
6 Correct 73 ms 74232 KB Output is correct
7 Correct 73 ms 74232 KB Output is correct
8 Correct 74 ms 74232 KB Output is correct
9 Correct 73 ms 74232 KB Output is correct
10 Correct 77 ms 74360 KB Output is correct
11 Correct 1368 ms 243808 KB Output is correct
12 Correct 1156 ms 226752 KB Output is correct
13 Correct 2992 ms 245964 KB Output is correct
14 Correct 1286 ms 160236 KB Output is correct
15 Correct 2676 ms 245996 KB Output is correct
16 Correct 2784 ms 245852 KB Output is correct
17 Correct 69 ms 74232 KB Output is correct
18 Correct 68 ms 74488 KB Output is correct
19 Correct 73 ms 74488 KB Output is correct
20 Correct 82 ms 74360 KB Output is correct
21 Correct 73 ms 74360 KB Output is correct
22 Correct 73 ms 74360 KB Output is correct
23 Incorrect 73 ms 74488 KB Output isn't correct
24 Halted 0 ms 0 KB -