Submission #1216125

#TimeUsernameProblemLanguageResultExecution timeMemory
1216125GabrielIslands (IOI08_islands)C++20
37 / 100
744 ms196608 KiB
#include "bits/stdc++.h" using namespace std; struct Arista{ long long Siguiente, Peso; }; struct Hijo{ long long Valor_abierto, Valor_cerrado, _ndice; }; long long Menos = -2222222222222222; vector< vector<Arista> > Grafo; map< pair<long long, long long>, long long > Pesos; vector<bool> Visitados; vector<long long> Padres, Valor_de_los_nodos; vector< pair<long long, long long> > Nodos_que_hacen_los_ciclos, Memorizaci_n; long long Ciclante, Inicio_del_ciclo; set<long long> No_pasar_por_aqu_; vector<long long> _rbol_izquierdo, _rbol_derecho, Propagar_izquierdo, Propagar_derecho, Izquierdo, Derecho; void DFS(long long Nodo, long long Anterior){ Visitados[Nodo] = 1; Padres[Nodo] = Anterior; bool Padre_visitado = 0; for(auto E: Grafo[Nodo]){ if(Visitados[E.Siguiente]){ //Detectar el único ciclo del componente conexo. if(E.Siguiente == Anterior){ if(Padre_visitado){ Ciclante = Nodo; Inicio_del_ciclo = E.Siguiente; } else Padre_visitado = 1; } else { Ciclante = Nodo; Inicio_del_ciclo = E.Siguiente; } } else DFS(E.Siguiente, Nodo); } } bool o(Hijo &a, Hijo &b){ return a.Valor_abierto > b.Valor_abierto; } void PD(long long Nodo){ //Obtener los caminos más largos dentro de los subárboles de los nodos que forman los ciclos. Visitados[Nodo] = 1; bool Final = 1; vector<Hijo> Hijos; long long Cerrado = 0, Abierto = 0; for(auto E: Grafo[Nodo]){ if(!Visitados[E.Siguiente] and No_pasar_por_aqu_.count(E.Siguiente) == 0){ PD(E.Siguiente); Final = 0; Hijo Siguiente; Siguiente._ndice = E.Siguiente; Siguiente.Valor_abierto = Memorizaci_n[E.Siguiente].first; Siguiente.Valor_cerrado = Memorizaci_n[E.Siguiente].second; Hijos.push_back(Siguiente); Cerrado = max(Cerrado, Siguiente.Valor_cerrado); Abierto = max(Abierto, Siguiente.Valor_abierto + E.Peso); } } if(Final){ Memorizaci_n[Nodo] = {0, 0}; return; } sort(Hijos.begin(), Hijos.end(), o); if(Hijos.size() == 1) Cerrado = max(Cerrado, Hijos[0].Valor_abierto + Pesos[{Nodo, Hijos[0]._ndice}]); else Cerrado = max(Cerrado, Hijos[0].Valor_abierto + Pesos[{Nodo, Hijos[0]._ndice}] + Hijos[1].Valor_abierto + Pesos[{Nodo, Hijos[1]._ndice}]); Memorizaci_n[Nodo] = {Abierto, Cerrado}; } void Crear(long long i, long long d, long long p){ if(i == d){ _rbol_izquierdo[p] = Izquierdo[i]; _rbol_derecho[p] = Derecho[i]; return; } long long P = (i + d) / 2; Crear(i, P, p * 2); Crear(P + 1, d, p * 2 + 1); _rbol_izquierdo[p] = max(_rbol_izquierdo[p * 2], _rbol_izquierdo[p * 2 + 1]); _rbol_derecho[p] = max(_rbol_derecho[p * 2], _rbol_derecho[p * 2 + 1]); } void Propagar(long long p){ if(Propagar_izquierdo[p] != 0){ if(p * 2 < Propagar_izquierdo.size()) Propagar_izquierdo[p * 2] += Propagar_izquierdo[p]; if(p * 2 + 1 < Propagar_izquierdo.size()) Propagar_izquierdo[p * 2 + 1] += Propagar_izquierdo[p]; _rbol_izquierdo[p] += Propagar_izquierdo[p]; Propagar_izquierdo[p] = 0; } if(Propagar_derecho[p] != 0){ if(p * 2 < Propagar_derecho.size()) Propagar_derecho[p * 2] += Propagar_derecho[p]; if(p * 2 + 1 < Propagar_derecho.size()) Propagar_derecho[p * 2 + 1] += Propagar_derecho[p]; _rbol_derecho[p] += Propagar_derecho[p]; Propagar_derecho[p] = 0; } //cerr<<"Propagado. "<<p<<"\n"; } long long Consulta_izquierda(long long i, long long d, long long p, long long I, long long D){ if(D < I) return 0; Propagar(p); if(i >= I and d <= D) return _rbol_izquierdo[p]; if(i > D or d < I) return Menos; long long P = (i + d) / 2; return max(Consulta_izquierda(i, P, p * 2, I, D), Consulta_izquierda(P + 1, d, p * 2 + 1, I, D)); } long long Consulta_derecha(long long i, long long d, long long p, long long I, long long D){ if(D < I) return 0; Propagar(p); if(i >= I and d <= D) return _rbol_derecho[p]; if(i > D or d < I) return Menos; long long P = (i + d) / 2; return max(Consulta_derecha(i, P, p * 2, I, D), Consulta_derecha(P + 1, d, p * 2 + 1, I, D)); } void Actualizar_izquierdo(long long i, long long d, long long p, long long I, long long D, long long v){ if(D < I) return; Propagar(p); if(i >= I and d <= D){ _rbol_izquierdo[p] += v; if(i != d){ Propagar_izquierdo[p * 2] += v; Propagar_izquierdo[p * 2 + 1] += v; } return; } if(i > D or d < I) return; long long P = (i + d) / 2; Actualizar_izquierdo(i, P, p * 2, I, D, v); Actualizar_izquierdo(P + 1, d, p * 2 + 1, I, D, v); _rbol_izquierdo[p] = max(_rbol_izquierdo[p * 2], _rbol_izquierdo[p * 2 + 1]); } void Actualizar_derecho(long long i, long long d, long long p, long long I, long long D, long long v){ if(D < I) return; Propagar(p); if(i >= I and d <= D){ _rbol_derecho[p] += v; if(i != d){ Propagar_derecho[p * 2] += v; Propagar_derecho[p * 2 + 1] += v; } return; } if(i > D or d < I) return; long long P = (i + d) / 2; Actualizar_derecho(i, P, p * 2, I, D, v); Actualizar_derecho(P + 1, d, p * 2 + 1, I, D, v); _rbol_derecho[p] = max(_rbol_derecho[p * 2], _rbol_derecho[p * 2 + 1]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); long long n; cin>>n; Grafo.assign(n, vector<Arista>()); Visitados.assign(n, 0); Padres.assign(n, 0); Valor_de_los_nodos.assign(n, 0); Memorizaci_n.assign(n, {-2, -2}); for(long long i = 0; i < n; i++){ long long u, w; cin>>u>>w; u--; Arista A; A.Siguiente = u; A.Peso = w; Grafo[i].push_back(A); A.Siguiente = i; Grafo[u].push_back(A); Pesos[{i, u}] = max(w, Pesos[{i, u}]); Pesos[{u, i}] = max(w, Pesos[{u, i}]); } for(long long i = 0; i < n; i++){ if(!Visitados[i]){ DFS(i, -2); Nodos_que_hacen_los_ciclos.push_back({Ciclante, Inicio_del_ciclo}); swap(Nodos_que_hacen_los_ciclos.back().first, Nodos_que_hacen_los_ciclos.back().second); //cerr<<"-> "<<Nodos_que_hacen_los_ciclos.back().first<<" "<<Nodos_que_hacen_los_ciclos.back().second<<"\n"; } } //cerr<<"¿Aquí?\n"; vector< vector<long long> > Ciclos; for(long long i = 0; i < Nodos_que_hacen_los_ciclos.size(); i++){ //Guardar los ciclos. vector<long long> Ciclo; for(long long Actual = Nodos_que_hacen_los_ciclos[i].first; Actual != Nodos_que_hacen_los_ciclos[i].second; Actual = Padres[Actual]){ Ciclo.push_back(Actual); No_pasar_por_aqu_.insert(Actual); //cerr<<Actual<<"\n"; } Ciclo.push_back(Nodos_que_hacen_los_ciclos[i].second); No_pasar_por_aqu_.insert(Nodos_que_hacen_los_ciclos[i].second); Ciclos.push_back(Ciclo); } //cerr<<"Ciclado.\n"; long long Respuesta_final = 0; Visitados.assign(n, 0); for(auto E: Ciclos){ //Encontrar la mejor respuesta de cada ciclo. long long m = E.size(), Respuesta = 0; Izquierdo.assign(m, 0); Derecho.assign(m, 0); _rbol_izquierdo.assign(m * 4 + 2, 0); _rbol_derecho.assign(m * 4 + 2, 0); Propagar_izquierdo.assign(m * 4 + 2, 0); Propagar_derecho.assign(m * 4 + 2, 0); for(long long i = 0; i < m; i++){ PD(E[i]); Respuesta = max(Respuesta, max(Memorizaci_n[E[i]].first, Memorizaci_n[E[i]].second)); Izquierdo[i] = Memorizaci_n[E[i]].first; Derecho[i] = Memorizaci_n[E[i]].first; Valor_de_los_nodos[E[i]] = Memorizaci_n[E[i]].first; } //cerr<<"Dinámico.\n"; long long Acumulada = 0; for(long long i = 1; i < m; i++){ Acumulada += Pesos[{E[i], E[i - 1]}]; Derecho[i] += Acumulada; } Derecho[0] += Acumulada + Pesos[{E[0], E[m - 1]}]; long long Longitud_del_ciclo = Derecho[0]; Acumulada = Pesos[{E[0], E[m - 1]}]; for(long long i = m - 1; i > 0; i--){ Izquierdo[i] += Acumulada; Acumulada += Pesos[{E[i], E[i - 1]}]; } Crear(0, m - 1, 1); //cerr<<"Creado.\n"; for(long long i = 0; i < m; i++){ long long Posible = max(Consulta_izquierda(0, m - 1, 1, 0, i - 1), Consulta_izquierda(0, m - 1, 1, i + 1, m - 1)) + Valor_de_los_nodos[E[i]]; Respuesta = max(Respuesta, Posible); //cerr<<"Consulta izquierda.\n"; Posible = max(Consulta_derecha(0, m - 1, 1, 0, i - 1), Consulta_derecha(0, m - 1, 1, i + 1, m - 1)) + Valor_de_los_nodos[E[i]]; Respuesta = max(Respuesta, Posible); //cerr<<"Consulta derecha.\n"; if(i == m - 1) continue; Actualizar_izquierdo(0, m - 1, 1, 0, m - 1, Pesos[{E[i], E[i + 1]}]); Actualizar_derecho(0, m - 1, 1, 0, m - 1, -Pesos[{E[i], E[i + 1]}]); long long Valor_izquierdo_del_siguiente = Consulta_izquierda(0, m - 1, 1, i + 1, i + 1), Valor_derecho_del_siguiente = Consulta_derecha(0, m - 1, 1, i + 1, i + 1); Actualizar_izquierdo(0, m - 1, 1, i + 1, i + 1, -Valor_izquierdo_del_siguiente); Actualizar_derecho(0, m - 1, 1, i + 1, i + 1, Longitud_del_ciclo - Valor_derecho_del_siguiente); } Respuesta_final += Respuesta; } cout<<Respuesta_final; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...