글 읽기 - 메모리 초과 질문입니다

whworjs7946 3년 전 0

코드는 다음과 같습니다.
입력을 받은 후 각 정점에 대해 bfs를 한 뒤 discovered에 초기 정점으로부터의 거리를 저장해서, 가장 먼 거리를 리턴합니다.
이 값들을 정점과 같이 묶어서 priorityqueue에 담아서, score가 바뀔 때 까지 계속 꺼내어 ret에 저장합니다.
저장한 후 ret를 정렬하여 답을 출력합니다.
메모리는 128MB제한인데, 이 문제의 n값은 최대 50입니다.
bfs가 끝나면 메모리를 전부 반환하기도 하고, 딱히 큰 배열을 선언하지도 않았고, n은 50이 최대인데 메모리 초과를
받았습니다.
아무리 생각해도 이해가 가지 않습니다.
제가 놓치고 있는 부분이 어디일까요?

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n;
vector<int> adj[51];

int getScore(int src){
	queue<int> q;
	vector<int> discovered(n + 1, -1);
	q.push(src);
	discovered[src] = 0;

	while(!q.empty()){
		int here = q.front();
		q.pop();

		for(int i = 0; i < adj[here].size(); ++i){
			int there = adj[here][i];
			if(discovered[there] != -1) continue;
			discovered[there] = discovered[here] + 1;
			q.push(there);
		}
	}

	int ret = -1;
	for(int i = 0; i < discovered.size(); ++i){
		ret = max(ret, discovered[i]);
	}

	return ret;
}

int main(int argc, char* argv[]) {
	cin >> n;
	int a, b;
	cin >> a >> b;
	while(a != -1 || b != -1){
		adj[a].push_back(b);
		adj[b].push_back(a);
		cin >> a >> b;
	}

	priority_queue<pair<int, int>> pq;
	for(int i = 1; i < n + 1; ++i){
		pq.push(make_pair(-getScore(i), i));
	}

	int score = -pq.top().first;
	vector<int> ret;
	while(true){
		if(score != -pq.top().first) break;
		ret.push_back(pq.top().second);
		pq.pop();
	}

	sort(ret.begin(), ret.end());
	printf("%d %d\n", score, ret.size());

	for(int i = 0; i < ret.size(); ++i){
		cout << ret[i] << " ";
	}
}

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

문제

문제

출처

ICPC

메모리 초과 질문입니다

whworjs7946 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말