oj.uz

Submission #48045

# Submission time Handle Problem Language Result Execution time Memory
48045 2018-05-09T14:08:54 Z E869120 Beads and wires (APIO14_beads) C++14
13 / 100
 1000 ms 408 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, A[100009], B[100009], C[100009], e[10], f[10], g[10][10], maxn;

int main() {
	cin >> N;
	for (int i = 0; i < N - 1; i++) { cin >> A[i] >> B[i] >> C[i]; A[i]--; B[i]--; }

	int d[10] = { 0,1,2,3,4,5,6,7,8,9 };

	do {
		for (int i = 0; i < N; i++) { e[i] = 0; f[i] = 0; }
		int cnt = 0; bool OK = true;
		for (int i = 0; i < N - 1; i++) {
			if (d[A[i]] < d[B[i]]) { g[B[i]][e[B[i]]] = A[i]; e[B[i]]++; f[B[i]] += C[i]; }
			else { g[A[i]][e[A[i]]] = B[i]; e[A[i]]++; f[A[i]] += C[i]; }
		}
		for (int i = 0; i < N; i++) {
			if (e[i] >= 3) OK = false;
			if (e[i] == 2 && (e[g[i][0]] >= 1 && e[g[i][1]] >= 1)) OK = false;
			if (e[i] == 2) cnt += f[i];
		}
		if (OK == true) maxn = max(maxn, cnt);
	} while (next_permutation(d, d + N));

	cout << maxn << endl;
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 203 ms 384 KB Output is correct
3 Correct 196 ms 384 KB Output is correct
4 Correct 202 ms 384 KB Output is correct
5 Correct 196 ms 384 KB Output is correct
6 Correct 209 ms 376 KB Output is correct
7 Correct 192 ms 384 KB Output is correct
8 Correct 223 ms 384 KB Output is correct
9 Correct 198 ms 408 KB Output is correct
10 Correct 184 ms 384 KB Output is correct
11 Correct 192 ms 408 KB Output is correct
12 Correct 185 ms 376 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 203 ms 384 KB Output is correct
3 Correct 196 ms 384 KB Output is correct
4 Correct 202 ms 384 KB Output is correct
5 Correct 196 ms 384 KB Output is correct
6 Correct 209 ms 376 KB Output is correct
7 Correct 192 ms 384 KB Output is correct
8 Correct 223 ms 384 KB Output is correct
9 Correct 198 ms 408 KB Output is correct
10 Correct 184 ms 384 KB Output is correct
11 Correct 192 ms 408 KB Output is correct
12 Correct 185 ms 376 KB Output is correct
13 Execution timed out 1075 ms 256 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 203 ms 384 KB Output is correct
3 Correct 196 ms 384 KB Output is correct
4 Correct 202 ms 384 KB Output is correct
5 Correct 196 ms 384 KB Output is correct
6 Correct 209 ms 376 KB Output is correct
7 Correct 192 ms 384 KB Output is correct
8 Correct 223 ms 384 KB Output is correct
9 Correct 198 ms 408 KB Output is correct
10 Correct 184 ms 384 KB Output is correct
11 Correct 192 ms 408 KB Output is correct
12 Correct 185 ms 376 KB Output is correct
13 Execution timed out 1075 ms 256 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 203 ms 384 KB Output is correct
3 Correct 196 ms 384 KB Output is correct
4 Correct 202 ms 384 KB Output is correct
5 Correct 196 ms 384 KB Output is correct
6 Correct 209 ms 376 KB Output is correct
7 Correct 192 ms 384 KB Output is correct
8 Correct 223 ms 384 KB Output is correct
9 Correct 198 ms 408 KB Output is correct
10 Correct 184 ms 384 KB Output is correct
11 Correct 192 ms 408 KB Output is correct
12 Correct 185 ms 376 KB Output is correct
13 Execution timed out 1075 ms 256 KB Time limit exceeded
14 Halted 0 ms 0 KB -