글 읽기 - LCA 메모리 초과 질문

rkdgh98 3년 전 0

각각 노드의 조상을 벡터로 만들어서 부여한 뒤 마지막에 선형으로 탐색하는 방식으로 풀어보았습니다.

최대한 스택메모리를 아끼려고 전역변수도 사용해보았는데

채점 94% 즈음에서 메모리초과가 발생합니다..

vector를 100000개 이상 만들어서 발생하는걸까요?

메모리 초과 발생 이유를 잘 모르겠어서 질문 드려봅니다

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<int> con[50001]; // 연결된 두 정점
vector<int> parent[50001]; //parent[n] == n번 노드의 조상노드 vector
vector<int> tmp;

//트리 부모찾으면서 각각의 노드에 조상 vector 추가하기
void findParent(int now)
{
	tmp.push_back(now);
	parent[now] = tmp;
	int s = con[now].size();
	for (int i = 0; i < s; i++)
	{
		if (parent[con[now][i]].empty())
		{
			findParent(con[now][i]);
		}
	}
	tmp.pop_back();
}

int main()
{
	cin.tie(NULL); cin.sync_with_stdio(false);
	cin >> N;
	int a, b;
	for (int i = 0; i < N-1; i++)
	{
		cin >> a >> b;
		con[a].push_back(b);
		con[b].push_back(a);
	}
	parent[1].push_back(1);
	findParent(1);
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		int sa = parent[a].size();
		int sb = parent[b].size();
		int minsize = min(sa, sb);
		int ans= 1;
		for (int j = 1; j < minsize; j++)
		{
			if (parent[a][j] == parent[b][j])
			{
				ans = parent[a][j];
			}
		}
		cout << ans << '\n';
	}
}

slah007 3년 전 1

unsigned short가 0 ~ 65535 를 표현하므로 int대신 쓰면 메모리 초과를 없앨수는 있습니다만 어차피 TLE를 받을 것 같습니다.

일단 parent에 조상의 vector를 모두 다 집어넣는거 자체가 사용하면 안되는 로직입니다. vector를 대입한다는건 결국 복사가 이루어져야 하므로 일직선으로 이루어진 트리에 대해 1+2+...(N-1)= O(N^2)번의 복사가 필요해요.

rkdgh98 3년 전 0

그렇군요!! 감사합니다 다른 방법을 생각해봐야겠어요

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

문제

문제

출처

ICPC

LCA 메모리 초과 질문

rkdgh98 3년 전 0

slah007 3년 전 1

rkdgh98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말