oj.uz

Submission #127507

# Submission time Handle Problem Language Result Execution time Memory
127507 2019-07-09T13:13:41 Z E869120 Balanced Tree (info1cup18_balancedtree) C++14
10 / 100
 17 ms 508 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)

int N, A[18], B[18], P[18], dist[18][18];

void solve() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) dist[i][j] = (1 << 29);
	}
	for (int i = 1; i <= N - 1; i++) {
		dist[A[i]][B[i]] = 1;
		dist[B[i]][A[i]] = 1;
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
	vector<int>vec;
	for (int i = 1; i <= N; i++) {
		if (P[i] == -1) vec.push_back(i);
	}

	int ans = (1 << 30), rem = 0;

	for (int i = 0; i < (1 << vec.size()); i++) {
		for (int j = 0; j < vec.size(); j++) {
			if ((i & (1 << j)) == 0) P[vec[j]] = 0;
			else P[vec[j]] = 1;
		}

		int maxn = 0;
		for (int j = 1; j <= N; j++) {
			int minx = (1 << 30);
			for (int k = 1; k <= N; k++) {
				if (j != k && P[j] == P[k]) minx = min(minx, dist[j][k]);
			}
			maxn = max(maxn, minx);
		}
		if (ans > maxn) {
			ans = maxn; rem = i;
		}
	}

	for (int i = 0; i < vec.size(); i++) {
		if ((rem & (1 << i)) == 0) P[vec[i]] = 0;
		else P[vec[i]] = 1;
	}
	if (ans == (1 << 30)) ans = -1;

	printf("%d\n", ans);
	if (ans != -1) {
		for (int i = 1; i <= N; i++) { if (i >= 2) printf(" "); printf("%d", P[i]); }
		printf("\n");
	}
}

int main() {
	int T; scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		scanf("%d", &N);
		for (int j = 1; j <= N - 1; j++) {
			scanf("%d%d", &A[j], &B[j]);
		}
		for (int j = 1; j <= N; j++) scanf("%d", &P[j]);

		solve();
	}
	return 0;
}

Compilation message

balancedtree.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
balancedtree.cpp: In function 'void solve()':
balancedtree.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec.size(); j++) {
                   ~~^~~~~~~~~~~~
balancedtree.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
balancedtree.cpp: In function 'int main()':
balancedtree.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int T; scanf("%d", &T);
         ~~~~~^~~~~~~~~~
balancedtree.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
   ~~~~~^~~~~~~~~~
balancedtree.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &A[j], &B[j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
balancedtree.cpp:68:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int j = 1; j <= N; j++) scanf("%d", &P[j]);
                                ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 17 ms 376 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)
3 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 17 ms 376 KB Output is correct
3 Runtime error 2 ms 368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)
6 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)
8 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 3 ms 404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 2 ms 380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 3 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)
19 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)
20 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)