# Smaltimento sostanze tossiche 23/100(1 wrong ans, i rimanenti out of memory)

**URL:** <https://forum.olinfo.it/t/smaltimento-sostanze-tossiche-23-100-1-wrong-ans-i-rimanenti-out-of-memory/8463>\
**Category:** Aiuto\
**Created:** [16 Agosto 2023, 3:40pm UTC](https://forum.olinfo.it/t/smaltimento-sostanze-tossiche-23-100-1-wrong-ans-i-rimanenti-out-of-memory/8463 "2023-08-16T15:40:04Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Kronos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/kronos/32/1694_2.png) [@Kronos](https://forum.olinfo.it/u/Kronos)\
**Post date:** [16 Agosto 2023, 3:40pm UTC](https://forum.olinfo.it/t/smaltimento-sostanze-tossiche-23-100-1-wrong-ans-i-rimanenti-out-of-memory/8463/1 "2023-08-16T15:40:04Z")

</div>

Ciao, stavo provando a fare [oii\_smaltimento](https://training.olinfo.it/#/task/oii_smaltimento/statement), ma fa solo 23/100. Riesce a fare i subtask 1-2-3-5 (Nel 4 fallisce l’ ultimo test) e tutto il resto va fuori memory limit. Per l’errore non ho idea di cosa sia, ma forse è un caso limite o una svista nel codice che si attiva solo in certi casi, mentre per il memory limit credo che la priority queue per qualche motivo si popoli di pair\<cost, conn\> per qualche motivo inutili (è l’unica struttura dati di dimensione variabile nel programma). Avete qualche suggerimento? Grazie mille!

Descrizione dell’algoritmo:  
L’algoritmo è una sorta di Dijkstra/BFS dal nodo N(il “barile vuoto” che producono le trasformazioni che non producono niente) al nodo 0 (Il barile di OI\_2) in un grafo in cui ogni processo di conversione è stato trasformato in un “fascio” di archi, che ho chiamato conn, e il verso di ogni conn è stato invertito.

L’idea è che un barile arrivato al nodo N ho costo 0 per essere smaltito, per cui tutti i tipi di barili che si possono trasformare in N richiedono 1. A questo punto ogni tipo di barile costa 1 + la somma dei costi di tutti i barili in cui viene trasformato.

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

#define f first
#define s second

#define ll long long
#define llu long long unsigned
#define oo INT_MAX;

#define pb push_back
#define rb pop_back

#define d(x) //cerr << __LINE__ << ": " << #x << " = " << x << endl

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vi> mi;

struct conn{
  vi to; int from;
  conn(vi to, int from): to(to), from(from){};
  conn(){};
  bool operator<(conn other) const{ return from < other.from; }
};

long long smaltisci(int N, int M, vector<int> A, vector<vector<int>> B) {
  vector<vector<conn>> AL(N+1);
  for(int p=0; p<M; p++){
    if(B[p].empty()) B[p] = {N};
    for(int t: B[p]){
      AL[t].pb(conn(B[p], A[p]));
    }
  }

  set<pair<int, conn>> frontiera = {};
  for(conn c: AL[N]){
    if(c.to.size()==1){ 
      frontiera.insert({1, c});
    }
  }

  vi cost(N+1, INT_MAX); cost[N] = 0;
  vi FC(N+1, INT_MAX); cost[N] = 0;

  conn curr; int cc;
  while(cost[0] == INT_MAX){
    curr=frontiera.begin() -> s; 
    cc=frontiera.begin() -> f; 
    frontiera.erase(frontiera.begin());
    if(cost[curr.from] == INT_MAX) cost[curr.from] = cc;
    else continue;

    for(conn c: AL[curr.from]){
      if(cost[c.from] != INT_MAX) continue;

      int val = 1;
      for(int t: c.to) if(cost[t] == INT_MAX or t == 0){
        val = 0; 
        break;
      }else val += cost[t];
      if(val and val<FC[c.from]){
        frontiera.insert({val, c});

        if(FC[c.from] != INT_MAX) frontiera.erase(frontiera.lower_bound({FC[c.from], c}), frontiera.upper_bound({FC[c.from], c}));
        FC[c.from] = val;
      }
    }
  }

  return cost[0];
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [16 Agosto 2023, 8:54pm UTC](https://forum.olinfo.it/t/smaltimento-sostanze-tossiche-23-100-1-wrong-ans-i-rimanenti-out-of-memory/8463/2 "2023-08-16T20:54:17Z")

</div>

Il problema riguarda l’array AL(N+1) con dimensione N = 100000 e AL[t].pb(conn(B[p], A[p])) dove l’array B[p] ha anch’esso dimensione N per cui la memoria richiesta è N\*N \> 512 MB.  
Pertanto è necessario ridurre la complessità dell’array AL().

---

<div class="post-metadata">

**Author:** ![Kronos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/kronos/32/1694_2.png) [@Kronos](https://forum.olinfo.it/u/Kronos)\
**Post date:** [17 Agosto 2023, 2:37pm UTC](https://forum.olinfo.it/t/smaltimento-sostanze-tossiche-23-100-1-wrong-ans-i-rimanenti-out-of-memory/8463/3 "2023-08-17T14:37:09Z")

</div>

Grazie! Ho risolto sostituendo gli struct conn con gli indici A\_i, ora fa 90/100. Inoltre ho tolto un int overflow error usando i long long: ora la task 12 non dà più wrong ans ma TLE. Guardando i limiti del subtask (tutti i valori di A\_i sono distinti) credo che sia qualcosa del tipo una lunghissima catena in cui ogni barile si trasforma in tutti i successivi(così la parte del codice in cui cerco tutti i tipi di barile che posso smaltire usando solo i processi di cui conosco il costo diventa in O(N))… per questo subtask stavo pensando che probabilmente è più efficente una DP che itera dall’ ultimo elemento della catena al primo, ma dai limiti del subtask non saprei come ricostruire la catena senza un algoritmo che come minimo va in O(N^2), quindi avrebbe la stessa efficenza… Comunque grazie ancora!

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [17 Agosto 2023, 5:08pm UTC](https://forum.olinfo.it/t/smaltimento-sostanze-tossiche-23-100-1-wrong-ans-i-rimanenti-out-of-memory/8463/4 "2023-08-17T17:08:42Z")

</div>

E quindi con una priority\_queue() risolveresti anche il task 12. Si tratta di inserire nella coda le sostanze da smaltire Ai con i costi di smaltimento Ci crescenti delle relative sostanze.

---

<div class="post-metadata">

**Author:** ![Kronos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/kronos/32/1694_2.png) [@Kronos](https://forum.olinfo.it/u/Kronos)\
**Post date:** [19 Agosto 2023, 7:06am UTC](https://forum.olinfo.it/t/smaltimento-sostanze-tossiche-23-100-1-wrong-ans-i-rimanenti-out-of-memory/8463/5 "2023-08-19T07:06:40Z")

</div>

Scusa ma continua a non funzionarmi 😓 Ho usato la priority queue e anche emplace al posto di push, ma continua a richiedere 2+ secondi. Sai che cosa può essere? Grazie mille

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

#define f first
#define s second

#define ll long long

typedef pair<ll,int> ii;
typedef vector<ll> vi;
typedef vector<vi> mi;

ll smaltisci(int N, int M, vector<int> A, vector<vector<int>> B) {
  vector<vector<int>> AL(N+1);
  for(int p=0; p<M; p++){
    if(B[p].empty()) B[p] = {N};
    for(int t: B[p]) AL[t].emplace_back(p);
  }
  // Ci Ai
  priority_queue<ii, vector<ii>, greater<ii>> frontiera = {};
  for(int p: AL[N]) if(B[p].size()==1) frontiera.emplace(1, p);

  vi cost(N+1, INT_MAX); cost[N] = 0;

  ii curr;
  while(cost[0] == INT_MAX){
    curr=frontiera.top(); 
    frontiera.pop();
    if(curr.f < cost[A[curr.s]]) cost[A[curr.s]] = curr.f;
    else continue;

    for(int p: AL[A[curr.s]]){
      if(cost[A[p]] != INT_MAX) continue;

      ll val = 1;
      for(ll t: B[p]) if(cost[t] == INT_MAX or t == 0){
        val = 0; 
        break;
      }else val += cost[t];

      if(val) frontiera.emplace(val, p);
    }
  }

  return cost[0];
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [19 Agosto 2023, 1:03pm UTC](https://forum.olinfo.it/t/smaltimento-sostanze-tossiche-23-100-1-wrong-ans-i-rimanenti-out-of-memory/8463/6 "2023-08-19T13:03:41Z")

</div>

Attenzione che INT\_MAX corrisponde a 2147483647 il max valore per un int, mentre stai utilizzando, invece, una variabile di tipo long long.

---

<div class="post-metadata">

**Author:** ![Kronos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/kronos/32/1694_2.png) [@Kronos](https://forum.olinfo.it/u/Kronos)\
**Post date:** [19 Agosto 2023, 1:45pm UTC](https://forum.olinfo.it/t/smaltimento-sostanze-tossiche-23-100-1-wrong-ans-i-rimanenti-out-of-memory/8463/7 "2023-08-19T13:45:29Z")

</div>

100/100, grazie 😃