글 읽기 - 시간 초과

dominic2009 6년 전 0

4%에서 시간 초과가 발생하는데 틀린 점을 모르겠습니다.

도와주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <map>
using namespace std;

struct Node {
	int pre;
	long long color;
}node[100001];

int N, K, r, A[100001], B[100001], chk[100001];
map<long long, bool> mp;

void _paint() {
	for (int i = 0; i < N; i++)
		chk[i] = 0;
	int a, b, c, tmp;
	scanf("%d%d%d", &a, &b, &c);

	if (a == b)
		return;

	int i_a = 0;
	tmp = a;
	A[0] = a;
	chk[A[0]] = 1;
	while (A[i_a] != 0 && i_a <= 1000) {
		i_a++;
		tmp = node[tmp].pre;
		A[i_a] = tmp;
		chk[A[i_a]] = 1;
	}

	int i_b = 0;
	tmp = b;
	B[0] = b;
	while (chk[B[i_b]] == 0) {
		i_b++;
		tmp = node[tmp].pre;
		B[i_b] = tmp;
	}

	for (int i = 0; A[i] != B[i_b]; i++)
		node[A[i]].color = c;
	for (int i = 0; B[i] != B[i_b]; i++)
		node[B[i]].color = c;
}

void _move() {
	int a, b;
	scanf("%d%d", &a, &b);
	int _pre = node[a].pre;
	node[a].pre = b;
}

void _count() {
	for (int i = 0; i < N; i++)
		chk[i] = 0;
	int a, b, tmp;
	scanf("%d%d", &a, &b);

	int i_a = 0;
	tmp = a;
	A[0] = a;
	chk[A[0]] = 1;
	while (A[i_a] != 0 && i_a <= 1000) {
		i_a++;
		tmp = node[tmp].pre;
		A[i_a] = tmp;
		chk[A[i_a]] = 1;
	}

	int i_b = 0;
	tmp = b;
	B[0] = b;
	while (chk[B[i_b]] == 0) {
		i_b++;
		tmp = node[tmp].pre;
		B[i_b] = tmp;
	}

	mp.clear();

	for (int i = 0; A[i] != B[i_b]; i++)
		mp.insert({ node[A[i]].color, true });
	for (int i = 0; B[i] != B[i_b]; i++)
		mp.insert({ node[B[i]].color, true });

	printf("%d\n", mp.size());
}

int main() {
	scanf("%d%d", &N, &K);
	for (int i = 1; i < N; i++) {
		node[i].pre = 0;
		node[i].color = 0;
	}
	for (int i = 0; i < K; i++) {
		scanf("%d", &r);
		if (r == 1)
			_paint();
		else if (r == 2)
			_move();
		else
			_count();
	}
	return 0;
}

dominic2009 6년 전 1

함수 마다 chk 배열을 초기화 시켜서 그랬습니다.

해결했습니다.

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

문제

문제

출처

ICPC

시간 초과

dominic2009 6년 전 0

dominic2009 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말