oj.uz

답안 #134593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134593 2019-07-23T05:05:56 Z 임유진(#3241) Telegraph (JOI16_telegraph) C++14
0 / 100
 2 ms 380 KB 
#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 && !chk[A[x]]) 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 == N) dfs(1, i);
		if(nr > 0) 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 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 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 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 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 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 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 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -