oj.uz

Submission #103725

# Submission time Handle Problem Language Result Execution time Memory
103725 2019-04-02T09:10:21 Z E869120 Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 2615 ms 245980 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 <= 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 GG = 2; if (pos == root) GG = G;
	int V = vec[max(0, (int)vec.size() - GG)];
	if (vec.size() < GG) 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 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 (rem >= 1) {
			G = 1000000;
		}
		else G++;
		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:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (vec.size() < GG) V = 0;
      ~~~~~~~~~~~^~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < lis[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
mousetrap.cpp:68: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:70: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 72 ms 74232 KB Output is correct
2 Correct 75 ms 74232 KB Output is correct
3 Correct 70 ms 74232 KB Output is correct
4 Correct 79 ms 74204 KB Output is correct
5 Correct 71 ms 74232 KB Output is correct
6 Correct 78 ms 74188 KB Output is correct
7 Correct 73 ms 74232 KB Output is correct
8 Correct 79 ms 74196 KB Output is correct
9 Correct 76 ms 74232 KB Output is correct
10 Correct 70 ms 74232 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1174 ms 243704 KB Output is correct
2 Correct 1030 ms 226696 KB Output is correct
3 Correct 2615 ms 245980 KB Output is correct
4 Correct 1232 ms 160104 KB Output is correct
5 Correct 2344 ms 245904 KB Output is correct
6 Correct 2374 ms 245852 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 74232 KB Output is correct
2 Correct 75 ms 74232 KB Output is correct
3 Correct 70 ms 74232 KB Output is correct
4 Correct 79 ms 74204 KB Output is correct
5 Correct 71 ms 74232 KB Output is correct
6 Correct 78 ms 74188 KB Output is correct
7 Correct 73 ms 74232 KB Output is correct
8 Correct 79 ms 74196 KB Output is correct
9 Correct 76 ms 74232 KB Output is correct
10 Correct 70 ms 74232 KB Output is correct
11 Incorrect 75 ms 74288 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 74232 KB Output is correct
2 Correct 75 ms 74232 KB Output is correct
3 Correct 70 ms 74232 KB Output is correct
4 Correct 79 ms 74204 KB Output is correct
5 Correct 71 ms 74232 KB Output is correct
6 Correct 78 ms 74188 KB Output is correct
7 Correct 73 ms 74232 KB Output is correct
8 Correct 79 ms 74196 KB Output is correct
9 Correct 76 ms 74232 KB Output is correct
10 Correct 70 ms 74232 KB Output is correct
11 Correct 1174 ms 243704 KB Output is correct
12 Correct 1030 ms 226696 KB Output is correct
13 Correct 2615 ms 245980 KB Output is correct
14 Correct 1232 ms 160104 KB Output is correct
15 Correct 2344 ms 245904 KB Output is correct
16 Correct 2374 ms 245852 KB Output is correct
17 Incorrect 75 ms 74288 KB Output isn't correct
18 Halted 0 ms 0 KB -