글 읽기 - 메모리 초과 ㅠㅠ (답 스포)

p_ce1052 4년 전 0

메모리 초과 어떻게 고쳐야할지 감이 안잡힙니다 문제 답은 한참 고민해보다 모르겠어서 힌트글을 봤는데 역순으로 추적하는 것이었고 코드는 직접 구현했습니다. 자를 선들을 제외하고 나머지 선들을 연결해놓고 자르는 순서의 역순으로 연결해가며 비용을 계산합니다. 틀렸습니다가 나와야 하는데 뜬금 메모리 초과가.... 처음에는 vector을 이용했는데 vector가 입력이 더 들어올 것에 대비해서 요구한 크기 이상으로 capacity를 넉넉하게 잡는 것이 원인인가 해서 정적 배열로 바꿨는데도 해결이 안되네요

#include<iostream>
#include<vector>
using namespace std;
int p[100001];
int connect_from[100000];
int connect_to[100000];
int cut[100000];
bool check[100000];

int find(int a){
	if(p[a]<0) return a;
	p[a]=find(p[a]);
	return p[a];
}

void yunion1(int a,int b){
	a=find(a);
	b=find(b);
	if(a==b) return;
	if(p[a]<p[b]){
		p[a]+=p[b];
		p[b]=a;
	}
	else{
		p[b]+=p[a];
		p[a]=b;
	}
	return;
}

long long yunion2(int a,int b){
	a=find(a);
	b=find(b);
	if(a==b) return 0;
	long long cost1=p[a]*-1;
	long long cost2=p[b]*-1;
	if(p[a]<p[b]){
		p[a]+=p[b];
		p[b]=a;
	}
	else{
		p[b]+=p[a];
		p[a]=b;
	}
	return cost1*cost2;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1; i<=n; i++) p[i]=-1;
	
	for(int i=0; i<n; i++) cin>>connect_from[i]>>connect_to[i];
	
	for(int i=0; i<q; i++){ //cut할 연결들에 표시 
		cin>>cut[i];
		check[cut[i]-1]=true;
	}
	for(int i=0; i<q; i++){  //표시되지 않은 연결들은 끝까지 남아있으므로 연결한다. 
		if(!check[i]) yunion1(connect_from[i],connect_to[i]);
	}
	long long cost=0;
	
	for(int i=q-1; i>=0; i--){ //끊는 순서의 역순으로 연결해가며 비용을 계산한다.  
		cost+=yunion2(connect_from[cut[i]-1],connect_to[cut[i]-1]);
	}
	cout<<cost;
}

pichulia 4년 전 0

간선의 개수는 m개입니다.

p_ce1052 4년 전 0

저런실수를...감사합니다 제정신이 아니었나봐요

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

문제

문제

출처

ICPC

메모리 초과 ㅠㅠ (답 스포)

p_ce1052 4년 전 0

pichulia 4년 전 0

p_ce1052 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말