글 읽기 - 반례가 있을 까요?

lyzqm 6년 전 1

disjoint set으로 센터와 기업을 묶어 주면서 길이도 더해줍니다

I 3 1

I 1 2

I 4 5

I 5 6

여기서

I 2 5를 추가하면

연결해주면ㅅ ㅓ 기존에 연결되어있던 부분들의 길이들도 갱신해줍니다.

물론 E 3이면 7, E 1이면 5이구요.

잘나오는데 뭐가 틀린걸까요?

#include <cstdio>
int N;
int par[20001];
int dist[20001];
inline int abs(int x) { return x < 0 ? -x : x; }
void init() {
	for (int n = 1;n <= N;n++) par[n] = n, dist[n] = 0;
}
int find(int x, int d) {
	dist[x] += d;
	if (x == par[x]) return x;
	return par[x] = find(par[x], d);
}
void merge(int u, int v) {
	int d = dist[v] + abs(v - u) % 1000;
	find(u, d);
	par[v] = u;
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &N);
		init();
		char c;
		while (scanf(" %c", &c), c != 'O') {
			if (c == 'E') {
				int u;
				scanf("%d", &u);
				printf("%d\n", dist[u]);
			}
			else {
				int u, v;
				scanf("%d%d", &u, &v);
				merge(u, v);
			}
		}
	}
	return 0;
}

sgchoi5 6년 전 1

SEERC 문제는 대회에서 사용했던 TC 가 공개되어 있습니다. 그거 한 번 써보세요.

http://gooddaytocode.blogspot....

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

문제

문제

출처

ICPC

반례가 있을 까요?

lyzqm 6년 전 1

sgchoi5 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말