글 읽기 - 시간초과 오류입니다 ㅠㅠ

gogoshin85 7년 전 0

각학생마다 원하는학생 번호를 넣고

for 문으로 원하는 학생에게 이동하게 하였습니다.

그 과정에서 사이클이 발생하면 그 사이클의 depth 를 더해주고

한번 방문한 학생은 다시 가지 않게 하였습니다.

생각해보면 불필요한 loop 가 없어 보이는데 왜 시간초과가 날까요 ㅠ

#include <iostream>

using namespace std;

int RESULT;

class Student 
{
public:
	int		nWanted;
	int		status; 
	int		nDepth;
};

Student *stu = new Student[100000];

void VisitNext(int idx, int status, int depth)
{
	if (stu[idx].status != -1 && stu[idx].status != status)
	{
		return;
	}

	if (stu[idx].status == -1)
	{
		stu[idx].status = status;
		stu[idx].nDepth = depth;
		VisitNext(stu[idx].nWanted, status, depth + 1);
	}
	else
	{
		RESULT += (depth - stu[idx].nDepth);
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);

	int T;
	cin >> T;

	for (unsigned int i = 0; i < T; i++)
	{
		RESULT = 0;

		int N;
		cin >> N;
		
		for (unsigned int j = 1; j <= N; j++)
		{
			cin >> stu[j].nWanted;
			stu[j].status = -1;
		}

		for (unsigned int j = 1; j <= N; j++)
		{
			VisitNext(j, j, 0);
		}

		cout << N - RESULT << endl;
	}

	delete[] stu;
	return 0;
}

jsh 7년 전 1

위 코드에서

입출력을 printf/scanf로 바꿔주시면 됩니다

gogoshin85 7년 전 0

정말 그렇게 하니깐 되네요 ㄷㄷ

감사합니다.

그런데 도대체 무슨차이죠??

jsh 7년 전 0

속도가 더빨라요 ㅎㅎ

그래서 입출력만 바꿨을때 통과되는 문제들이 의외로 많이 있더라구요

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

문제

문제

출처

ICPC

시간초과 오류입니다 ㅠㅠ

gogoshin85 7년 전 0

jsh 7년 전 1

gogoshin85 7년 전 0

jsh 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말