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;
}
}