글 읽기 - 2533 사회망서비스 시간초과 질문입니다

juhongkim2 7년 전 0

트리는 간선리스트로 구현했는데

어째 시간초과가 계속 나오네요 어느부분이 잘못된건지 알려주세요ㅠㅠ

#include <stdio.h>

typedef struct{
	int parent,child;
}Edge;

Edge e[2000010];
int cnt[1000010];
int check[1000010];
int d[1000010][2];
int n,m;

int Min(int n1, int n2)
{
	if(n1>n2)
		return n2;

	return n1;
}

void Quick(int left, int right)
{
	int l,r,pivot;
	Edge tmp;

	if(left<right){
		l=left-1;
		r=right+1;
		pivot=e[(left+right)/2].parent;

		while(1){
			while(e[++l].parent<pivot);
			while(e[--r].parent>pivot);

			if(l>=r)
				break;

			tmp=e[l];
			e[l]=e[r];
			e[r]=tmp;
		}

		Quick(left,l-1);
		Quick(r+1,right);
	}
}

void DFS(int vertex)
{
	int i,p;

	check[vertex]=1;

	for(i=cnt[vertex-1];i<cnt[vertex];i++){
		p=e[i].child;

		if(check[p]==0){
			DFS(p);
			d[vertex][0]+=d[p][1];
			d[vertex][1]+=Min(d[p][0],d[p][1]);
		}
	}

	d[vertex][1]++;
}

int main()
{
	int i;

	scanf("%d",&n);
	m=n-1;

	for(i=0;i<m;i++){
		scanf("%d %d",&e[i].parent, &e[i].child);
		e[i+m].child=e[i].parent;
		e[i+m].parent=e[i].child;
	}

	m*=2;
	Quick(0,m-1);

	for(i=0;i<m;i++){
		cnt[e[i].parent]++;
	}

	for(i=1;i<=n;i++){
		cnt[i]=cnt[i-1]+cnt[i];
	}

	DFS(1);

	printf("%d\n",Min(d[1][1],d[1][0]));

	return 0;
}

tae826 7년 전 0

퀵소트 쓰신거 같은데 퀵소트가 아무래도 최악의 경우엔 O(N^2) 이라 그런게 아닐까여 #include <algorithm> 한 후 std::sort()써보세요

juhongkim2 7년 전 0

algorithm 헤더파일 안쓰고 문제를 푸는 연습을 해야해서...ㅠㅠ

정렬부분 말고는 문제가 없는걸까요?

tae826 7년 전 0

WA가 아닌 TLE라면 정렬문제가 맞는것 같네요 Merge Sort 나 Heap Sort 쓰는게 어떨까요

juhongkim2 7년 전 0

답변감사합니다!

양방향처리해주는 과정에서 저런식으로 하니 TLE가 나오네요

이유는 잘모르겟지만요;;;

merge sort로도 해봐야갰네요

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

문제

문제

출처

ICPC

2533 사회망서비스 시간초과 질문입니다

juhongkim2 7년 전 0

tae826 7년 전 0

juhongkim2 7년 전 0

tae826 7년 전 0

juhongkim2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말