| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 391803 |
2021-04-19T23:59:42 Z |
ocarima |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
14912 KB |
#include<bits/stdc++.h>
using namespace std;
// PES 2021 - abril. "Rey de la Atlantida" (100 pts)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define lli long long int
#define vi vector<int>
#define vlli vector<long long int>
#define pii pair<int, int>
#define plli pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define repv(x, v) for(auto (x) : (v))
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(x) cout << #x << " = " << x << ", "
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b) cout << x[i] << ", "; cout << "]\n"
#define pb push_back
#define nl "\n"
#define MAX_N 100003
#define MAX_M 300003
#define MAX_K 22
#define INF (1ll << 62)
#define costo first
#define extremos second
#define izq first
#define der second
struct DSU
{
int tam;
vector<int> grupo;
void inicializa(int t){
tam = t;
grupo.resize(t + 1);
iota(grupo.begin(), grupo.end(), 0);
}
void reinicia(){ iota(grupo.begin(), grupo.end(), 0); }
int obtengrupo(int u){ return (grupo[u] == u) ? u : grupo[u] = obtengrupo(grupo[u]); }
bool une(int u, int v){
u = obtengrupo(u), v = obtengrupo(v);
if (u == v) return false;
grupo[u] = v;
return true;
}
};
lli n, m, k, g, ncomp, ciudadCentral, peso, u, v, maxbits;
lli maxflujo, ganancia, res;
pair<lli, pii> originales[MAX_M];
vector<pair<lli, pii > > obligatorios, optimos;
pii nuevos[MAX_K];
lli personas[MAX_N], subarbol[MAX_N], nivel[MAX_N], padre[MAX_N], costos[MAX_N];
int etiqueta[MAX_N], nodoreal[MAX_N];
DSU mst;
void dfs(const vector<vi>& hijos, int nodo, int pad){
subarbol[nodo] = personas[nodoreal[nodo]];
nivel[nodo] = nivel[pad] + 1;
padre[nodo] = pad;
repv(h, hijos[nodo]){
if (h == pad) continue;
dfs(hijos, h, nodo);
subarbol[nodo] += subarbol[h];
}
}
int main()
{
fastio;
cin >> n >> m >> k;
rep(i, 1, m) cin >> originales[i].extremos.izq >> originales[i].extremos.der >> originales[i].costo;
rep(i, 1, k) cin >> nuevos[i].izq >> nuevos[i].der;
rep(i, 1, n) cin >> personas[i];
sort(originales + 1, originales + 1 + m); // ORDENALOS PARA QUE SE PROCESEN EN EL ORDEN DE UN MST
mst.inicializa(n);
// PASO 1.
// CONECTA TODAS LAS CIUDADES POSIBLES MEDIANTE LOS CAMINOS NUEVOS.
// ESTO PERMITIRA DETERMINAR UN CONJUNTO DE CAMINOS ORIGINALES OBLIGATORIOS (LOS MINIMOS NECESARIOS PARA CONECTAR LO QUE LOS NUEVOS NO PUEDEN CONECTAR)
mst.reinicia();
rep(i, 1, k) mst.une(nuevos[i].izq, nuevos[i].der);
// USA LOS CAMINOS ORIGINALES MAS BARATOS PARA CONECTAR LO QUE QUEDE DISCONEXO
rep(i, 1, m) if (mst.une(originales[i].extremos.izq, originales[i].extremos.der))
obligatorios.emplace_back(originales[i]);
// PASO 2.
// FIJA LOS CAMINOS OBLIGATORIOS Y UNIFICA LAS CIUDADES DE CADA COMPONENTE EN UN SOLO NODO.
mst.reinicia();
repv(cam, obligatorios) mst.une(cam.extremos.izq, cam.extremos.der); // CREA EL GRAFO QUE USA LOS CAMINOS OBLIGATORIOS
// UNIFICA LAS CIUDADES DE CADA COMPONENTE EN UN SOLO NODO "VIRTUAL"
rep(i, 1, n){
g = mst.obtengrupo(i); // CADA NODO VA A QUEDAR UNIDO AL NODO "RAIZ" DE SU COMPONENTE
if (g != i) personas[g] += personas[i]; // PARA CADA NODO QUE ESTE UNIDO A ALGUIEN MAS, UNE SUS PERSONAS A EL
}
// REETIQUETA LOS GRUPOS PARA QUE VAYAN DE UNO EN UNO (ESTO ES SOLO PARA FACILITARNOS LA CODIFICACION MAS ADELANTE)
rep(i, 1, n){
g = mst.obtengrupo(i);
if (g == i){
nodoreal[++ncomp] = i;
etiqueta[i] = ncomp;
}
}
ciudadCentral = etiqueta[mst.obtengrupo(1)];
// REAPUNTA LOS NODOS A LOS QUE SE CONECTAN LOS CAMINOS NUEVOS PARA QUE SE CONECTEN AL NODO VIRTUAL
rep(i, 1, k){
nuevos[i].izq = etiqueta[mst.obtengrupo(nuevos[i].izq)];
nuevos[i].der = etiqueta[mst.obtengrupo(nuevos[i].der)];
}
// REAPUNTA LAS ARISTAS A LOS NODOS VIRTUALES
rep(i, 1, m){
originales[i].extremos.izq = etiqueta[mst.obtengrupo(originales[i].extremos.izq)];
originales[i].extremos.der = etiqueta[mst.obtengrupo(originales[i].extremos.der)];
}
// PASO 3.
// USA LOS CAMINOS ORIGINALES PARA CONSTRUIR UN MST DE LOS NODOS UNIFICADOS, ESTE MST ES EL QUE SERA REEMPLAZADO POR LOS CAMINOS NUEVOS, PERO NECESITAMOS SUS COSTOS PARA SABER EL MAXIMO QUE PODEMOS PONER EN LOS CAMINOS NUEVOS.
mst.reinicia();
rep(i, 1, m) if (mst.une(originales[i].extremos.izq, originales[i].extremos.der))
optimos.emplace_back(originales[i]);
// PASO 4.
// PRUEBA TODAS LAS POSIBILIDADES DE ARBOL MINIMO QUE SE PUEDEN FORMAR USANDO LOS CAMINOS NUEVOS
bool ciclo;
DSU arbol;
arbol.inicializa(ncomp);
rep(msk, 0, (1 << k) - 1){
arbol.reinicia();
ciclo = false;
vector<vi> hijos(ncomp + 1);
vector<bool> optimoUsado(optimos.size(), false);
// MANEJA CADA BIT COMO UNO DE LOS CAMINOS NUEVOS
rep(bit, 0, (k - 1)) if (msk & (1 << bit)){
u = nuevos[bit + 1].izq;
v = nuevos[bit + 1].der;
if (arbol.une(u, v)){
// CREA LA ARISTA DEL ARBOL
hijos[u].emplace_back(v);
hijos[v].emplace_back(u);
}
else{
ciclo = true;
break;
}
}
if (ciclo) continue; // SI HUBO CICLO, NO PRUEBES ESE ARBOL
// SI FALTA ALGUN COMPONENTE DE UNIR UNELO
rep(i, 0, optimos.size() - 1){
u = optimos[i].extremos.izq;
v = optimos[i].extremos.der;
if (arbol.une(u, v)){
// AGREGA LA ARISTA AL ARBOL
hijos[u].emplace_back(v);
hijos[v].emplace_back(u);
optimoUsado[i] = true;
}
}
// HAZ UNA BUSQUEDA DESDE LA CIUDAD CENTRAL PARA SABER CUANTAS PERSONAS PASAN POR CADA CAMINO CON ESE ARBOL
dfs(hijos, ciudadCentral, 0);
// PROCESO CLAVE!!!
// CADA CAMINO NUEVO QUE SE USA AGREGA UN CICLO EN EL MST ORIGINAL. DE ESE CICLO SE DEBE ELIMINAR UNA ARISTA Y CONVIENE ELIMINAR LA ARISTA DE MAYOR COSTO.
// CUANDO SE AGREGA MAS DE UN CAMINO NUEVO SE CREA MAS DE UN CICLO, EN GENERAL CADA CICLO QUE SE CREA SE ELIMINA UNA ARISTA DE LOS CAMINOS ORIGINALES
// LA OBSERVACION IMPORTANTE ES QUE UN CAMINO NUEVO PUEDE PERTENECER A MAS DE UN CICLO, EN ESE CASO, EL COSTO MAXIMO QUE PUEDE TENER EL CAMINO NUEVO
// ES EL MENOR DE TODOS LOS CAMINOS QUE SE HAYAN ELIMINADO QUE ESTEN EN ALGUN CICLO COMUN. DE OTRA FORMA, SI EL CAMINO NUEVO TUVIERA UN COSTO MAS ALTO
// SE PODRIA CONSTRUIR UN MST USANDO EL CAMINO ORIGINAL Y ELIMINANDO EL NUEVO.
// HECHA LA DFS HAY QUE USAR PROBAR TODAS LAS ARISTAS "OPTIMAS" QUE FUERON ELIMINADAS Y MARCAR LOS CICLOS EN COMUN PARA PODER ASIGNAR LOS COSTOS.
rep(i, 1, ncomp) costos[i] = INF;
rep(i, 0, optimos.size() - 1){
if (optimoUsado[i]) continue; // LOS QUE YA ESTAN EN EL ARBOL NO ES NECESARIO REVISARLOS.
u = optimos[i].extremos.izq;
v = optimos[i].extremos.der;
peso = optimos[i].costo;
if (nivel[u] < nivel[v]) swap(u, v); // HAZ QUE u SEA EL NODO MAS PROFUNDO DE AMBOS
while (nivel[u] > nivel[v]){ // IGUALA LOS NIVELES
costos[u] = min(costos[u], peso); // VE MARCANDO EN CADA NODO EL MENOR PESO
u = padre[u];
}
while (u != v){ // AVANZA HASTA QUE SEAN EL MISMO
costos[u] = min(costos[u], peso);
costos[v] = min(costos[v], peso);
u = padre[u];
v = padre[v];
}
}
// FINALMENTE CALCULA LA GANANCIA PARA CADA CAMINO NUEVO QUE AGREGASTE AL ARBOL
ganancia = 0;
rep(bit, 0, (k - 1)) if (msk & (1 << bit)){
u = nuevos[bit + 1].izq;
v = nuevos[bit + 1].der;
if (u == padre[v]) swap(u, v);
ganancia += subarbol[u] * costos[u];
}
if (ganancia > res){
maxbits = max(maxbits, (lli) __builtin_popcount(msk));
res = ganancia;
}
}
cout << res << endl;
}
Compilation message
toll.cpp: In function 'void dfs(const std::vector<std::vector<int> >&, int, int)':
toll.cpp:15:29: warning: unnecessary parentheses in declaration of 'h' [-Wparentheses]
15 | #define repv(x, v) for(auto (x) : (v))
| ^
toll.cpp:68:5: note: in expansion of macro 'repv'
68 | repv(h, hijos[nodo]){
| ^~~~
toll.cpp: In function 'int main()':
toll.cpp:15:29: warning: unnecessary parentheses in declaration of 'cam' [-Wparentheses]
15 | #define repv(x, v) for(auto (x) : (v))
| ^
toll.cpp:99:9: note: in expansion of macro 'repv'
99 | repv(cam, obligatorios) mst.une(cam.extremos.izq, cam.extremos.der); // CREA EL GRAFO QUE USA LOS CAMINOS OBLIGATORIOS
| ^~~~
toll.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define rep(i, a, b) for(int i = (a); i <= (b); i++)
| ^
toll.cpp:167:13: note: in expansion of macro 'rep'
167 | rep(i, 0, optimos.size() - 1){
| ^~~
toll.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define rep(i, a, b) for(int i = (a); i <= (b); i++)
| ^
toll.cpp:190:13: note: in expansion of macro 'rep'
190 | rep(i, 0, optimos.size() - 1){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
5 ms |
460 KB |
Output is correct |
| 6 |
Correct |
3 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
5 ms |
460 KB |
Output is correct |
| 6 |
Correct |
3 ms |
460 KB |
Output is correct |
| 7 |
Correct |
218 ms |
14788 KB |
Output is correct |
| 8 |
Correct |
222 ms |
14816 KB |
Output is correct |
| 9 |
Correct |
216 ms |
14736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
5 ms |
460 KB |
Output is correct |
| 6 |
Correct |
3 ms |
460 KB |
Output is correct |
| 7 |
Correct |
218 ms |
14788 KB |
Output is correct |
| 8 |
Correct |
222 ms |
14816 KB |
Output is correct |
| 9 |
Correct |
216 ms |
14736 KB |
Output is correct |
| 10 |
Correct |
2104 ms |
14792 KB |
Output is correct |
| 11 |
Execution timed out |
2585 ms |
14912 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
