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

Aiuto
1

Ciao, stavo provando a fare oii_smaltimento, 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.

#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];
}
2

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().

3

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!

4

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.

5

Scusa ma continua a non funzionarmi :sweat: 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

#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];
}
6

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

7

100/100, grazie :smiley: