글 읽기 - 예제는 무리없이 돌아가는데 왜틀리는지 모르겠어용 ㅠㅠ

gktgnjftm 5년 전 0

유니온 파인드를 이용하여 풀었는데

동맹을 맺으면 동맹을 맺기전 root정점과 동맹을 맺은후의 root정점끼리 병력을 합치고, 병력을 지웁니다

전쟁을 해서 국가가 만약에 망하면, 해당 국가의 parent배열을 -1로 가리키게 하여,

나중에 find함수를 통해 갱신되는 정점들을 -1로 갱신이 되면서, 국가가 망함을 표현했습니다

병력이 남아있을때 국가로 인정이 되어서 넣었는데

어떤 반례가 있을지 궁금합니당

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
using namespace std;
typedef long long ll;
#define INF 1000000000
typedef pair<int, int> P;
typedef pair<int, pair<ll, char>> PP;
typedef pair<pair<int, int>, pair<int, int>> PPP;
typedef pair<ll, ll> p;
int gox[4] = { 0,0,1,-1 };
int goy[4] = { 1,-1,0,0 };
int n, m;
int army[100005];
int parent[100005];
int find(int u) {
	if (parent[u] == -1) return -1;
	if (u == parent[u]) return u;
	return parent[u] = find(parent[u]);
}
void uni(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	parent[u] = v;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &army[i]);
	for (int i = 1; i <= n; i++) parent[i] = i;
	for (int i = 1; i <= m; i++) {
		int what, first, second;
		scanf("%d%d%d", &what, &first, &second);
		if (what == 1) {
			first = find(first); // 합치기전
			uni(first, second);
			int firsttop = find(first); //합친후
			army[firsttop] += army[first]; // 병력 합치기
			army[first] = 0; // 합쳤으니 병력 지우기
		}
		else {
			int firsttop = find(first);
			int secondtop = find(second);
			if (army[firsttop] == army[secondtop]) {
				parent[firsttop] = -1; // 두 동맹 다 멸망
				parent[secondtop] = -1;
				army[firsttop] = 0;
				army[secondtop] = 0;
			}
			else if (army[firsttop] < army[secondtop]) {
				parent[firsttop] = -1; 
				army[secondtop] -= army[firsttop];
				army[firsttop] = 0;
				uni(firsttop, secondtop); // 망한쪽이 왼쪽 인자로 넘어감
			}
			else if (army[firsttop] > army[secondtop]) {
				parent[secondtop] = -1;
				army[firsttop] -= army[secondtop];
				army[secondtop] = 0;
				uni(secondtop, firsttop); // 망한쪽이 왼쪽인자로 넘어감
			}
		}
	}
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		if (find(i) == -1) continue; // 나라 멸망
		else {
			if (army[i] == 0) continue; // 병력이 없음
			v.push_back(army[i]);
		}
	}
	printf("%d\n", v.size());
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		printf("%d ", v[i]);
	}
	return 0;
}

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

문제

문제

출처

ICPC

예제는 무리없이 돌아가는데 왜틀리는지 모르겠어용 ㅠㅠ

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말