글 읽기 - [C++] 어떤 부분에서 틀렸는지 모르겠네요.. 33%에서 틀리네요

eddy5360 3년 전 0

이것저것 넣어봤지만 반례를 찾을 수가 없네요..

도움 주시면 감사하겠습니다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
typedef long long int llt;

const llt MAX = 1e4 + 1;
llt n, q, k;
pii parent[MAX];

void init() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

llt getParent(llt c) {
	if (parent[c].first == c) return c;
	return parent[c].first = getParent(parent[c].first);
}

void unionParent(llt a, llt b) {
	llt ap = getParent(a);
	llt bp = getParent(b);
	ap < bp ? parent[bp].first = ap : parent[ap].first = bp;
}

int main() {
	init();
	cin >> n >> q >> k;
	for (llt cost, i = 1; i <= n; ++i) {
		cin >> cost;
		parent[i] = make_pair(i, cost); // 부모, 비용
	}
	for (llt a, b, i = 0; i < q; ++i) {
		cin >> a >> b;
		unionParent(a, b); // 합
	}

	sort(parent, parent + 1 + n); // 부모, 비용 순서로 정렬
	llt currIdx = 0; llt totalCost = 0;
	for (llt i = 1; i <= n; ++i) {
		// 부모(루트) 하나에 가장 작은 비용 하나만 더해줌
		if (parent[i].first > currIdx) {
			totalCost += parent[i].second;
			currIdx = parent[i].first;
		}
		// 필요한 비용이 가지고 있는 돈보다 커지는 경우
		if (totalCost > k) {
			cout << "Oh no\n"; return 0;
		}
	}
	// 모든 친구들을 사귈 수 있는 경우
	cout << totalCost << '\n';

	return 0;
}

lsh23 3년 전 0

혹시 해결하셨나요? 저도 33%에서 틀려가지고요.

hongsbin 3년 전 0

저두...

deserve82 3년 전 13

아마 33% 에서 틀리신다면

5 4 100
1 1 1 1 1
1 5
2 4
4 3
5 4

이게 반례가 될 가능성이 높습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] 어떤 부분에서 틀렸는지 모르겠네요.. 33%에서 틀리네요

eddy5360 3년 전 0

lsh23 3년 전 0

hongsbin 3년 전 0

deserve82 3년 전 13

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말