글 읽기 - 왜 틀렸는 지 모르겠어요

rdd6584 4년 전 0

제가 작성한 로직입니다.

블루간선으로 연결되어 있는 노드들을 전부 union함.
이때 union된 횟수를 max라고 한다.

새로운 disjoint-set을 하나 더 만들어서,

레드간선으로 연결된 양끝 노드가 동일한 블루집합에 속해 있다면
union을 하고 이때 union된 횟수를 min이라고 했을 때,

max-min <= k <= max면 항상 가능하다고 생각했는데, 어떤 경우에 안되는걸까요?

#include <cstdio>
#include <memory.h>
#include <cstring>
#include <vector>
#include <deque>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <functional>
#include <iostream>
#include <set>
#include <list>
#include <map>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const ll MOD = (ll)1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

priority_queue<int, vector<int>, greater<int>> pq;
vector<int> v;

int p[1000];
int rp[1000];

int rrotn[1000];
int rotn[1000];

struct edg {
	char c;
	int u, v;
} ed[1000000];

int find(int a) {
	if (p[a] == -1) return a;
	return p[a] = find(p[a]);
}

void merge(int a, int b) {
	a = find(a); b = find(b);
	if (a == b) return;
	rotn[a] += rotn[b];
	p[b] = a;
}

int rfind(int a) {
	if (rp[a] == -1) return a;
	return rp[a] = rfind(rp[a]);
}

void rmerge(int a, int b) {
	a = rfind(a); b = rfind(b);
	if (a == b) return;
	rrotn[a] += rrotn[b];
	rp[b] = a;
}

int main() {
	while (1) {
		int n, m, k;
		scanf("%d %d %d", &n, &m, &k);
		if (n == 0) return 0;

		memset(p, -1, sizeof(p));
		memset(rp, -1, sizeof(rp));
		fill(rotn, rotn + n, 1);
		fill(rrotn, rrotn + n, 1);

		for (int i = 0; i < m; i++) {
			scanf(" %c %d %d", &ed[i].c, &ed[i].u, &ed[i].v);
			ed[i].u--; ed[i].v--;
			if (ed[i].c == 'B')
				merge(ed[i].u, ed[i].v);
		}

		for (int i = 0; i < m; i++)
			if (ed[i].c == 'R' && find(ed[i].u) == find(ed[i].v))
				rmerge(ed[i].u, ed[i].v);

		int le = 0, ri = 0;
		for (int i = 0; i < n; i++) {
			if (find(i) == i) ri += rotn[i] - 1;
			if (rfind(i) == i) le += rrotn[i] - 1;
		}

		if (k >= ri - le && ri >= k) printf("1\n");
		else printf("0\n");
	}
}

lovinix 4년 전 1

다음과 같은 경우에 틀립니다

Input
6 8 1
R 1 2
B 1 3
B 1 4
R 3 4
B 2 5
B 2 6
R 5 6
R 2 3
0 0 0
Output
0
Answer
1

lovinix 4년 전 1

동일한 블루집합에 속해있지 않은 두 레드간선 (1->2, 2->3)을 이용해서 1->3 블루간선을 없앨수있어요

rdd6584 4년 전 1

갓비닉스님 진짜 감사합니다!!!

덕분에 편히 잠을 잘 수 있게 되었어요.

lovinix 4년 전 1

갓디디님만세 :fan:

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

문제

문제

출처

ICPC

왜 틀렸는 지 모르겠어요

rdd6584 4년 전 0

lovinix 4년 전 1

lovinix 4년 전 1

rdd6584 4년 전 1

lovinix 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말