글 읽기 - 시간초과 이유를 잘 모르겠습니다.

lokilo 4년 전 0

2%에서 한 30초 멈춰서 있다가 시간초과가 뜨는데 이유를 잘 모르겠습니다. 도움 부탁드립니다.

#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

class soya
{
public:
	int x, y;
};

class cmp
{
public:
	bool operator()(const soya& u, const soya& v)
	{
		if (u.x < v.x)
			return true;
		else if (u.x == v.x)
		{
			if (u.y < v.y)
				return 1;
			else
				return 0;
		}
		else
			return 0;

	}
};


soya e[500010];
int index[1010];
int chk[1010];

int main()
{
	//freopen("input.txt", "r", stdin);
	int N, M;
	int i, j;

	scanf("%d %d", &N, &M);
	int m = 0;

	for (j = 0; j < M; j++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		e[m].x = x;
		e[m].y = y;
		e[m + 1].y = x;
		e[m + 1].x = y;

		m += 2;
	}

	sort(e, e + m, cmp());

	int k = 0;
	for (i = 0; i < m; i++)
	{
		while (e[i].x >= k)
			index[k++] = i;
	}
	index[N+1] = m + 1;
	int ans = 0;

	for (i = 1; i <= N; i++)
	{
		if (chk[i] == 0)
		{
			ans++;
			queue <int> q;
			q.push(i);
			chk[i] = ans;
			int x;
			while (!q.empty())
			{
				x = q.front();
				q.pop();
				for (j = index[x]; j < index[x + 1]; j++)
				{
					if (chk[e[j].y] == 0)
					{
						chk[e[j].y] = ans;
						q.push(e[j].y);
					}
				}
			}
		}
	}

	printf("%d", ans);
	return 0;
}

qwer9412 4년 전 1

67번째 줄에 index[N+1] = m + 1;가 아니라 index[N+1] = m; 아닐까요?

예를 들어 N이2이면 47번째 줄 반복문 끝난 시점의 m이 4일텐데 e배열의 마지막 인덱스는 3이겠네요.

lokilo 4년 전 0

바꿔봐도 여전히 2%에서 한 30초 멈춘뒤에 시간초과가 발생하네요

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

문제

문제

출처

ICPC

시간초과 이유를 잘 모르겠습니다.

lokilo 4년 전 0

qwer9412 4년 전 1

lokilo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말