oj.uz

Submission #496955

# Submission time Handle Problem Language Result Execution time Memory
496955 2021-12-22T07:34:00 Z abc864197532 Balanced Tree (info1cup18_balancedtree) C++17
10 / 100
 4000 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define X first
#define Y second
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l) 
		cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x);
#else
#define test(x...) void(0);
#endif
const int N = 100000;

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector <vector <int>> dis(n, vector <int> (n, n + 87));
		for (int i = 0, u, v; i < n - 1; ++i) {
			cin >> u >> v, --u, --v;
			dis[u][v] = dis[v][u] = 1;
		}
		for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
		vector <int> a(n);
		for (int i = 0; i < n; ++i)
			cin >> a[i];
		int tans = 1 << 30, best = 0;
		for (int s = 0; s < 1 << n; ++s) {
			bool fail = false;
			for (int i = 0; i < n; ++i) {
				if (a[i] != -1 && (s >> i & 1) != a[i]) {
					fail = true;
				}
			}
			if (fail)
				continue;
			for (int d = n - 1; ~d; --d) {
				bool fail = false;
				for (int i = 0; i < n; ++i) {
					bool ok = false;
					for (int j = 0; j < n; ++j) if (j ^ i && dis[i][j] <= d && (s >> j & 1) == (s >> i & 1)) {
						ok = true;
					}
					if (!ok)
						fail = true;
				}
				if (!fail && tans > d) {
					tans = d, best = s;
				}
			}
		}
		if (tans == 1 << 30)
			tans = -1;
		cout << tans << endl;
		if (tans != -1) {
			for (int i = 0; i < n; ++i) 
				cout << (best >> i & 1) << ' ';
			cout << endl;
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 332 KB Output is correct
2 Correct 631 ms 364 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1033 ms 1088 KB Output isn't correct
2 Runtime error 207 ms 524292 KB Execution killed with signal 9
3 Execution timed out 4078 ms 392256 KB Time limit exceeded

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4057 ms 1460 KB Time limit exceeded
2 Runtime error 186 ms 524292 KB Execution killed with signal 9
3 Runtime error 202 ms 524292 KB Execution killed with signal 9

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 197 ms 524292 KB Execution killed with signal 9
2 Execution timed out 4062 ms 4444 KB Time limit exceeded
3 Execution timed out 4073 ms 16064 KB Time limit exceeded
4 Execution timed out 4057 ms 720 KB Time limit exceeded
5 Execution timed out 4062 ms 4420 KB Time limit exceeded
6 Execution timed out 4081 ms 98512 KB Time limit exceeded
7 Execution timed out 4065 ms 4420 KB Time limit exceeded
8 Execution timed out 4069 ms 568 KB Time limit exceeded
9 Execution timed out 4053 ms 4472 KB Time limit exceeded

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 332 KB Output is correct
2 Correct 631 ms 364 KB Output is correct
3 Incorrect 1033 ms 1088 KB Output isn't correct
4 Runtime error 207 ms 524292 KB Execution killed with signal 9
5 Execution timed out 4078 ms 392256 KB Time limit exceeded
6 Execution timed out 4057 ms 1460 KB Time limit exceeded
7 Runtime error 186 ms 524292 KB Execution killed with signal 9
8 Runtime error 202 ms 524292 KB Execution killed with signal 9
9 Runtime error 197 ms 524292 KB Execution killed with signal 9
10 Execution timed out 4062 ms 4444 KB Time limit exceeded
11 Execution timed out 4073 ms 16064 KB Time limit exceeded
12 Execution timed out 4057 ms 720 KB Time limit exceeded
13 Execution timed out 4062 ms 4420 KB Time limit exceeded
14 Execution timed out 4081 ms 98512 KB Time limit exceeded
15 Execution timed out 4065 ms 4420 KB Time limit exceeded
16 Execution timed out 4069 ms 568 KB Time limit exceeded
17 Execution timed out 4053 ms 4472 KB Time limit exceeded
18 Execution timed out 4064 ms 392232 KB Time limit exceeded
19 Runtime error 181 ms 524292 KB Execution killed with signal 9
20 Execution timed out 4014 ms 1644 KB Time limit exceeded
21 Runtime error 172 ms 524292 KB Execution killed with signal 9
22 Execution timed out 4072 ms 4528 KB Time limit exceeded