Ropes Escape (ropes)

Aiuto
1

Alcuni casi sono sbagliati dell’ultimo subtask sono sbagliati, ho provato a controllare il codice ma non capisco dove possa essere l’errore. Qualcuno può darmi un indizio?
Grazie in anticipo

#include  <stdio.h>
#include  <assert.h> 

// constraints
#define MAXN 100000

// input data
int N, i;
int  P[MAXN], T[MAXN];

int  main() {
	assert(1 == scanf("%d", &N));
	for(i=0; i<N; i++)
		assert(1 == scanf("%d", &P[i]));
	for(i=0; i<N; i++)
		assert(1 == scanf("%d", &T[i]));

	long  maxTime[MAXN] = {-1};
	long time = 0;

	for(i = 0; i < N; i++){
		if(T[i] > maxTime[P[i]]){
			if(maxTime[P[i]] != -1)
				time += maxTime[P[i]];

			maxTime[P[i]] = T[i];
		}
		else {
			time += T[i];
		}
	}

	printf("%d\n", time);
	return  0;
}
2

È un po’ difficile dare solo un inizio, il problema è veramente stupido, MAXN è 100000, questo significa che le celle vanno dalla 0 alla 99999, tuttavia in if(T[i] > maxTime[P[i]]), P[i] può essere anche 100000, basta quindi definire MAXN leggermente più grande (cosa che andrebbe fatta sempre per evitare errori del genere).
Tuttavia hai avuto abbastanza fortuna :sweat_smile:, infatti ci sono un paio di imprecisioni che fortunatamente non sono errori in questo caso ma potrebbero esserlo in altri:

  • Quando metti long maxTime[MAXN] = {-1}; non stai inizializzando tutto il vettore a -1 ma solo la prima casella, ma le restanti vengono messe uguali a 0, quindi in time += maxTime[P[i]]; non influiscono (se invece non avessi scritto = {-1} avrebbero assunto valori imprevedibili, essendo una variabile locale). Per rimediare basta usare un ciclo for o scrivere fill(maxTime,maxTime + MAXN,-1);.
  • Dovresti scrivere printf("%ld\n", time); e non printf("%d\n", time);, in quanto time è un long int, in questo caso non ci sono problemi di overflow in quanto per le limitazioni del problema basterebbe un int.
3

Grazie mille, non avevo notato che le limitazioni prevedevano che P[i] potesse essere anche
100000.

1 Mi Piace