답안 #134592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134592	2019-07-23T05:04:19 Z	임유진(#3241)	Telegraph (JOI16_telegraph)	C++14	0 / 100	3 ms	376 KB

telegraph

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;

const lint LINF = 1ll << 60;

int A[20], C[20];
bool chk[20];

void dfs(int x, int i) {
	chk[x] = true;
	if((i & (1 << x)) == 0) dfs(A[x], i);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int N;
	lint ans = LINF;
	int cnt[20];

	cin >> N;
	for(int i = 0; i < N; i++) cin >> A[i] >> C[i];

	for(int i = 0; i < N; i++) A[i]--;
	for(int i = 0; i < (1 << N); i++) {
		bool b = true;
		for(int j = 0; j < N; j++) {
			cnt[j] = 0;
			chk[j] = false;
		}
		for(int j = 0; j < N; j++) if((i & (1 << j)) == 0) cnt[A[j]]++;
		for(int j = 0; j < N; j++) if(cnt[j] > 1) b = false;
		if(!b) continue;
		for(int j = 0; j < N; j++) if(cnt[j] == 0) dfs(j, i);
		int nr = 0;
		for(int j = 0; j < N; j++) if(!chk[j]) nr++;
		if(nr > 0 && nr < N) continue;
		lint sum = 0ll;
		for(int j = 0; j < N; j++) if(i & (1 << j)) sum += C[j];
		//printf("i = %d, sum = %lld\n", i, sum);
		ans = min(ans, sum);
	}

	cout << ans;
	return 0;
}

Subtask #1

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Incorrect	2 ms	256 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #2

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Incorrect	2 ms	256 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #3

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Incorrect	2 ms	256 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Incorrect	2 ms	256 KB	Output isn't correct
21	Halted	0 ms	0 KB	-