Problemi con Licenziamenti

Aiuto
1

Salve, ho provato a fare il problema Licenziamenti, ma mi dà solo 20 punti.

L’algoritmo mi sembra corretto: creo una lista di adiacenza e per ogni nodo assegno ai figli il minore tra il minore che vi è prima del padre e il valore del padre, che rappresenta il minimo valore di bravura che vi è sopra del figlio.
A questo punto conto il numero di persone che hanno valori sopra di loro che sono minori del loro valore.

EDIT: Ricordo che non hanno funzionato solo alcune subtask.

Vi lascio qui sotto il codice.

#include <assert.h>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 100000
#define ll long long
ll counter = 0;
ll R[MAXN];
vector<ll> K[MAXN];
ll licenzia(ll N, ll* B, ll* C) {
  if(N==1) return 0;
  for(ll i=1;i<N;i++){
    R[i] = B[C[i]];
  }
  for(ll i=1;i<N;i++){
    K[C[i]].push_back(i);
  }
  for(auto k : K[0]){
    R[k]=B[0];
  }
  for(ll i=1;i<N;i++){
    for(auto k : K[i]){
      R[k]=min(R[i], B[i]);
    }
  }
  for(ll i=1;i<N;i++){
    if(R[i]<B[i]){
      counter++;
    }
  }/*
  for(ll i=1;i<N;i++){
    cout << R[i] << " " << B[i] << endl;
  }*/
  return counter;
}

ll B[MAXN], C[MAXN];

int main() {
    FILE *fr, *fw;
    ll N, i;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    assert(1 == fscanf(fr, "%d", &N));
    for(i=0; i<N; i++)
        assert(2 == fscanf(fr, "%d %d", &B[i], &C[i]));

    fprintf(fw, "%d\n", licenzia(N, B, C));
    fclose(fr);
    fclose(fw);
    return 0;
}`
2

heila, non ho capito perfettamente cosa intendi fare, potresti farmi un esempio?
mia sol:

io l’ho risolto con dfs

3

Si tratta praticamente di una dfs, in cui passo ad ogni ramo il minor valore che compare tra tutti i suoi precedenti. A quel punto conto quelli che hanno questo valore minore strettamente della loro bravura: se sì, vuol dire che hanno bravura maggiore di quella di un loro capo, e vanno quindi licenziati.
A livello teorico dovrebbe funzionare: è abbastanza semplice.

5

La tua “dfs” assume che i nodi con numerazione più bassa si trovino sempre più in alto dei nodi con numerazione più alta; per esempio: il nodo 5 non può essere padre del nodo 3.

1 Mi Piace
6

semplicemente io mi salvo il valore minimo incontrato come parametro per ogni dfs

1 Mi Piace
7

Capito!
Mi era proprio sfuggita come cosa.
Grazie mille.

8

cosi sai esattamente quali valori hai incontrato e sai con cosa confrontare

1 Mi Piace
9

giacomo ma la soluzione piu efficiente per questo problema quale sarebbe?

10

La soluzione più efficiente è O(N).
La dfs ha complessità O(V + E) ma siccome siamo in un albero V = E per cui diventa O(N).

11

ah okke grazie mille

12

Non ho usato dfs e neanche la lista delle adiacenze, ho trovato le foglie e sono andato da quelle su per l’albero fino ad incontrare un nodo già visitato e la soluzione dovrebbe essere O(N).

13

una soluzione iterativa è sicuramente più veloce di una ricorsiva, infatti mi chiedevo di come la tua soluzione fossi cosi veloce

14

Perfettamente d’accordo, inoltre il tempo per trovare le foglie è ampiamente compensato dal tempo risparmiato evitando di creare le liste di adiacenza ( a suon di pushback su un vector di vector).

15

esattamente, mi chiedevo infatti perché la tua soluzione era cosi veloce ahahha