Могу ли я уменьшить использование памяти в этом коде C ++?

#include <bits/stdc++.h>
using namespace std;

int n;

vector<bool> used;
vector<int> order, comp;

void dfs1 (int v,const vector<vector<int>>& g) {
used[v] = true;
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (!used[to])
dfs1 (to,g);
}
order.push_back (v);
}

void dfs2 (int v, int cl,const vector<vector<int>>& gt) {
comp[v] = cl;
for (size_t i=0; i<gt[v].size(); ++i) {
int to = gt[v][i];
if (comp[to] == -1)
dfs2 (to, cl,gt);
}
}

int main() {
int q1,q3;
cin>>q1>>n>>q3;

n*=2;
vector < vector<int> > g(n), gt(n);
vector< vector< int> > adj(q1+5);
int o,oo;
for(int i=0;i<q3;i++){
cin>>o>>oo;
if(oo<0){
oo+=1;
adj[o].push_back((oo*-1)*2+1);
} else{

oo-=1;
adj[o].push_back(oo*2);

}

}

for(int i=1;i<=q1;i++){

for(int j=0;j<adj[i].size();j++){
for(int k=0;k<adj[i].size();k++){

if(j!=k){
g[adj[i][j]^1].push_back(adj[i][k]);
gt[adj[i][k]].push_back(adj[i][j]^1);
}
} }
}used.assign (n+1, false);
for (int i=0; i<n; ++i)
if (!used[i])
dfs1 (i,g);

comp.assign (n+1, -1);
for (int i=0, j=0; i<n; ++i) {
int v = order[n-i-1];
if (comp[v] == -1)
dfs2 (v, j++,gt);
}

for (int i=0; i<n; ++i)
if (comp[i] == comp[i^1]) {
cout<<-1;
return 0;
}
vector<int> answ;

for (int i=0; i<n; i+=2) {
int ans = comp[i] > comp[i^1] ? i : i^1;
if(ans%2==0){
ans/=2;

ans++;
answ.push_back(ans);

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

Это код, который решает проблему, связанную с 2SAT. При вводе значения n = 200 000 этот код превышает ограничение памяти, которое составляет 512 мБ. Какие приемы я могу использовать, чтобы уменьшить использование памяти? Я уже пытался назначить векторы g и gt в основном коде, а затем в функции dfs и dfs2 я поставил g и gt, но это дало мне проблему с ограничением по времени. Как я могу оптимизировать этот код?

-1

Решение

Вы не используете g и gt одновременно. Так что очистите g и зарезервируйте gt после этого.
( comp.assign (n+1, -1); до этой строчки)

То же самое с б и комп.

used а также adj не используются одновременно. Очистить adj перед линией used.assign (n+1, false);

Попробуйте использовать adj как вектор стиля C ( int** ) и еще один вектор для индивидуальных размеров.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]