oj.uz

답안 #48045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48045 2018-05-09T14:08:54 Z E869120 구슬과 끈 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -