You are not logged in. Please login at www.codechef.com to post your questions!

×

Relocation truncated to fit error

The following program is giving a relocation truncated to fit error which I am not able to resolve, please help!!

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k;
vector<ll> mus(n);
bool edge[1000000][1000000]={};
vector<bool> vis(n,false);
vector<long long> sum(n,0);
int comp=-1;
void dfs(int s){
if(vis[s])return;
vis[s]=true;
sum[comp]=sum[comp]+mus[s];
for(int i=0;i<n;i++)
{
if(edge[s][i])dfs(i);
}
}
int main(){
ll t;
cin>>t;
while(t--){
cin>>n>>m>>k;
for(ll i=0;i<m;i++){int a,b;
cin>>a>>b;edge[a][b]=1;edge[b][a]=1;
}
for(ll i=0;i<n;i++)
cin>>mus[i];
for(ll i=0;i<n;i++)
{
if(!vis[i]){comp++;
dfs(i);}
}
if(comp<k-1){cout<<"-1\n";continue;}
sort(sum.begin(),sum.end());
long long suma=0;
int a=0,b=comp-1;for(ll i=0;i<k;i++){
if(i%2==0){suma=suma+sum[b];b--;}
else {suma=suma+sum[a];a++;}
}
cout<<suma<<"\n";
}
return 0;
}

asked 09 Dec '18, 20:37

karan26122001's gravatar image

2★karan26122001
11
accept rate: 0%


You just used 1 Terabytes of memory in edge[1000000][1000000]

Every question has a maximum memory limit given. Generally in Megabytes.

There is another way of storing connected components in a graph using less memory.

[Cpp] Simple dfs using vector

Geeksforgeeks Implementation

[Cpp] Simple dfs using Map

link

answered 09 Dec '18, 21:44

black_truce's gravatar image

5★black_truce
1297
accept rate: 27%

edited 11 Dec '18, 00:09

2

it's a bool, so it's 1 TeraByte imo

(10 Dec '18, 00:09) swetankmodi ♦♦6★

Oh yes, true. I've edited.

(10 Dec '18, 10:55) black_truce5★

Can a map also be used?

(10 Dec '18, 22:07) karan261220012★

Yes, you can use Map for dfs. I've added the simple implementation in the answer.

(11 Dec '18, 00:08) black_truce5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,901
×421

question asked: 09 Dec '18, 20:37

question was seen: 115 times

last updated: 11 Dec '18, 00:09