글 읽기 - 메모리 초과가 납니다 ㅠㅠ

gsh0910 3년 전 0

어느 부분이 메모리 초과를 일으켰는지 알려주시면 감사하겠습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAX = 100000 + 1;
int parent[MAX];

struct Edge{
	int v1, v2, c;
	
	bool operator < (Edge & edge){
		return c < edge.c;
	}
};

struct Star{
	int x,y,z;
};


int getparent(int a){
	if(parent[a] == a) return a;
	else return parent[a] = getparent(parent[a]);
}

void unionparent(int a, int b){
	a = getparent(a);
	b = getparent(b);
	if(a < b)	parent[b] = a;
	else		parent[a] = b;
}

int main(){
	vector<Edge> v;
	vector<Star> star;
	int n, m;
	int cmp[3];                                // 50번 줄에서 min_element를 사용하기 위한 선언
   
	cin >> n;
	for(int i=0; i<n; i++){
		int a, b,c;
		int distance;
		cin >> a >> b >> c;
		star.push_back({a,b,c});
		for(int j=0; j<star.size()-1; j++){
			cmp[0] = abs(star[j].x - a);
			cmp[1] = abs(star[j].y - b);
			cmp[2] = abs(star[j].z - c);
			
			distance = *min_element(cmp, cmp+3);
			v.push_back({j,i,distance});
		}
	}
	
	sort(v.begin(), v.end());
	double sum = 0;
	int line = 0;
	for(int t=0; t<MAX; t++)
		parent[t] = t;
	
	for(int k=0; k<v.size(); k++){
		if(getparent(v[k].v1) != getparent(v[k].v2)){
			unionparent(v[k].v1, v[k].v2);
			sum += v[k].c;
			line ++;
		}
		if(line == n-1)
			break;
	}

	cout << sum << '\n';
}

bupjae 3년 전 0

n 이 100000 일 때

v 안에 들어가는 원소의 개수는 100000 * 99999 / 2 = 4999950000 개 입니다.

각 원소는 int 3개 = 12 byte 이므로, 필요한 메모리의 양은 4999950000 * 12 = 약 56 TB 으로, 문제에서 주어진 제한 128 MB 를 훨씬 초과합니다.

gsh0910 3년 전 0

으앗,, 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

메모리 초과가 납니다 ㅠㅠ

gsh0910 3년 전 0

bupjae 3년 전 0

gsh0910 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말