Trasporti

Aiuto
1

Nel problema trasporti in gara ho totalizzato 90 punti, ma ora sottomettendo la stessa soluzione ho 72 punti a causa di un caso errato nel subtask 5 (il primo ad essere precisi). Per risolverlo uso la colorazione dell’albero e non capisco quale possa essere l’errore. Il mio codice è:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define MAXL 100010
int ris, appartiene[MAXL], zeri[MAXL], v[4*MAXL + 10];
vector< int >colleg[MAXL];
bool visited[MAXL];

void Visita(int p, int *briganti, int prec) {
	visited[p] = true;
	zeri[ p ] = max(prec, briganti[p]);
	for(vector< int >::iterator i = colleg[p].begin(); i != colleg[p].end(); i++) {
		if(visited[*i]) continue;
		Visita(*i, briganti, zeri[p]);
	}
	visited[p] = false;
}

void Dividi(int p, int q, int num) {
	visited[p] = true;
	appartiene[p]=num;
	for(vector< int >::iterator i = colleg[p].begin(); i != colleg[p].end(); i++) {
		if(*i == q || visited[*i]) continue;
		Dividi(*i,  q, num);
	}
	visited[p] = false;
}

bool Dfs(int p, int a, int *briganti) {
	if(p == a) { ris= briganti[a]; return true; }
	visited[ p ] = true;
	for(vector< int >::iterator i = colleg[p].begin(); i != colleg[p].end(); i++) {
		if(visited[ *i ]) continue;
		if(Dfs(*i, a, briganti)) { 
			ris = max(ris, briganti[p]);
			visited[p]=false; 
			return true;
		 }
	}
	visited[p] = false;
	return false;
}



int Sx(int p) { return p << 1; }
int Dx(int p) { return (p<<1) + 1; }

int Query(int p, int a, int i, int j, int pos) {
	if(i > a || j < p) return -1;
	if(i >= p && j <= a) return v[pos];
	return max(Query(p, a, i, (i+j)/2, Sx(pos)), Query(p, a, (i+j)/2 + 1, j, Dx(pos)));
}
void Costruisci(int p, int a, int pos, int *H) {
	if(p == a) { v[ pos ] = H[ p ]; return; }
	
	Costruisci(p, (p+a)/2, Sx(pos), H);
	Costruisci((p+a)/2 + 1, a, Dx(pos), H);
	
	v[pos] = max( Query(p, (p+a)/2, p, (p+a)/2, Sx(pos)), Query((p+a)/2 + 1, a, (p+a)/2 + 1, a, Dx(pos)));
}

void solve(int N, int Q, int *briganti, int *A, int *B, int *start, int *end, int *sol){
	int i;
	for(i=0; i<Q; i++) sol[i] = i;
	bool subtask2=true, subtask3=true, subtask5=true, subtask4=true;
	int contadiv=0, q=0;
	for(int i=0; i < N-1; i++) {
		if(briganti[i] != 1) { q=i; contadiv++; }
		colleg[ A[i] ].push_back( B[i] );
		colleg[ B[i] ].push_back( A[i] );
		if(A[i] != 0 && B[i]!= 0) subtask2=false;
		if(A[i] - B[i] > 1 || A[i]-B[i] < -1) subtask3=false;
	}
	for(int i=0; i < Q && subtask4; i++) if(start[i] != 0) subtask4=false;
	if(briganti[N-1] != 1) contadiv++;
	if(contadiv != 1) subtask5=false;
	if(subtask3) Costruisci(0, N-1, 1, briganti);
	if(subtask4) Visita(0, briganti, 0); 
	if(subtask5) {
		int c=1;
		appartiene[q]=0;
		for(vector< int >::iterator i = colleg[q].begin(); i != colleg[q].end(); i++, c++) Dividi(*i, q, c);
	}

	for(int i=0; i < Q; i++) {
		ris=0;
		if(subtask2) {
			if(start[i] == end[i]) ris = briganti[start[i]];
			else ris = max(briganti[start[i]], max(briganti[0], briganti[end[i]]));
		}
		else if(subtask3) {
			int parti = min(start[i], end[i]), arriva=max(start[i], end[i]);
		    ris = Query(parti, arriva, 0, N-1, 1);
		}
		else if(subtask4) ris=zeri[ end[i] ];
		else if(subtask5) {
			if(start[i]==q || end[i]==q) ris = briganti[q];
			else ris = (appartiene[ start[i] ] != appartiene[ end[i] ]) ? briganti[q] : 1;
		}
		else Dfs(start[i], end[i], briganti);
		sol[i]=ris;
		//cout<<"Sol da "<<start[i]<<" a "<<end[i]<<" : "<<sol[i]<<endl;
	}
}

( http://pastebin.com/DTsN2HDJ )

2

Scusate, ho risolto mi ero dimenticato di considerare l’ultimo nodo ahaha

3

Bravo :wink:

Comunque in generale i test case non sono tutti uguali quindi non è detto che la vostra soluzione totalizzi stessi punti della gara.
4

In effetti io in gara avevo implementato una soluzione NlogN per il problema skyline che prendeva 100/100 mentre sul correttore totalizzava 72/100 se non sbaglio, comunque bastava una piccola modifica per farla stare entro i tempi limite.

5
In effetti io in gara avevo implementato una soluzione NlogN per il problema skyline che prendeva 100/100 mentre sul correttore totalizzava 72/100 se non sbaglio, comunque bastava una piccola modifica per farla stare entro i tempi limite.

Caraz96

Com'è la soluzione nlogn per skyline? Ho provato con un range tree (per ripassarli un po') ma mi da 72

6

Io mi ero fatto un vettore di pair<int,int>, V[i]=make_pair(H[i],i), lo ordini in verso decrescente

per ogni posizione di B(indice centrale nel problema):
    controlli se H[B]!=V[i].first && H[B]!=Mprev(il massimo precedente a B)
    while(B>V[i].second)++i
7

Capito. Ho saputo di qualcuno che ha fatto 100/100 coi range tree, per questo chiedevo :stuck_out_tongue:

8

Io ho fatto 100 con un range tree per valuta. Il mio algoritmo è questo (fa 100 anche sul cms senza modifiche dalla gara):

Per ogni B (da 1 a N-2) trovi Ha =  max(0, B-1) e Hc = max(B+1, N-1). Se HB <= Ha && Hb <= Hc allora aumenti il contatore delle terne. Se implementi giusto il range tree è facile
9

Mi sa che è il mio range tree allora, perché faccio qualcosa di davvero molto simile.
Per ogni B da 1 a N-2 controllo la posizione del massimo da 0 a B, se è uguale a B passo al prossimo B, altrimenti controllo la posizione del massimo da B a N-1, se è uguale a B passo al prossimo B, altrimento aumento il contatore.

Menomale che in gara ho trovato subito la soluzione lineare

10

Anche io prima di trovare la soluzione O(N) avevo inizialmente implementato un RangeTree e, scorrendo B da 1 a N-2 incrementavo il contatore solo se RMQ(0,B) != RMQ(B,N-1).

E anche io andavo in TLE
11

Risolto, il problema era che per portare i valori di H in globale li copiavo in un vector con push_back :stuck_out_tongue: