글 읽기 - 메모리 초과 이유가 궁금합니다.

dksdmssh1212 4년 전 0

9퍼센트에서 메모리 초과가 뜹니다.

아마 62번째 줄에서 for문을 돌릴 때 p벡터에 너무 많은 요소가 들어가서 인 걸까요 ..

감사합니다.

#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;

struct GodHouse {
	int x, y;
};
struct path {
	int i, j;
	double d;
};
bool operator<(const path& a, const path& b) {
	return a.d < b.d;
}
int uf[1001] = {};
GodHouse godHouse[1001];
vector<path> p;
vector<pair<int, int> > alreadyExist;
double ret = 0;
int F(int x) {
	if (uf[x] == x)	return x;
	return uf[x] = F(uf[x]);
}
void U(int x, int y) {
	x = F(x);
	y = F(y);
	if (x == y)	return;
	uf[y] = x;
}
void kruskal() {
	sort(p.begin(), p.end());
	for (path i : p) {
		int ri = F(i.i);
		int rj = F(i.j);
		if (ri != rj) {
			uf[rj] = ri;
			ret += i.d;
		}
	}
	cout << setprecision(3) << ret << endl;
}
double getDist(GodHouse a, GodHouse b) {
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
int main() {
	int N, M;
	int a, b;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		uf[i + 1] = i + 1;
		cin >> godHouse[i + 1].x >> godHouse[i + 1].y;
	}
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		alreadyExist.push_back({ a, b });
		uf[b] = a;
	}
	for (int i = 0; i < alreadyExist.size(); i++) {
		for (int j = 1; j <= N - 1; j++) {
			for (int k = j + 1; k <= N; k++) {
				if (alreadyExist[i].first == j && alreadyExist[i].second == k) {
					continue;
				}
				p.push_back({ j, k, getDist(godHouse[j], godHouse[k]) });
			}
		}
	}
	kruskal();
	return 0;
}

djm03178 4년 전 0

맞습니다. 보아하니 alreadyExist에 있는 쌍들은 안 넣으려고 하신 것 같은데, 이렇게 하면 alreadyExist에 있는 쌍들이 안 들어가는 게 아니라 그 쌍들은 alreadyExist.size() - 1번 들어가고 나머지 쌍은 alreadyExist.size() 번만큼 들어갑니다.

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

문제

문제

출처

ICPC

메모리 초과 이유가 궁금합니다.

dksdmssh1212 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말