oj.uz

Submission #391804

# Submission time Handle Problem Language Result Execution time Memory
391804 2021-04-20T00:22:14 Z ocarima Toll (APIO13_toll) C++14
78 / 100
 2500 ms 8388 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
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, maxmsk;
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 invalido[(1 << 20) + 1];
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);

        maxmsk = (1 << k) - 1;
        rep(msk, 0, maxmsk){

            if (invalido[msk]) continue;

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

            res = max(res, ganancia);
        }


	cout << res << endl;
}

Compilation message

toll.cpp: In function 'void dfs(const std::vector<std::vector<int> >&, int, int)':
toll.cpp:16:29: warning: unnecessary parentheses in declaration of 'h' [-Wparentheses]
   16 | #define repv(x, v) for(auto (x) : (v))
      |                             ^
toll.cpp:70:5: note: in expansion of macro 'repv'
   70 |     repv(h, hijos[nodo]){
      |     ^~~~
toll.cpp: In function 'int main()':
toll.cpp:16:29: warning: unnecessary parentheses in declaration of 'cam' [-Wparentheses]
   16 | #define repv(x, v) for(auto (x) : (v))
      |                             ^
toll.cpp:101:9: note: in expansion of macro 'repv'
  101 |         repv(cam, obligatorios) mst.une(cam.extremos.izq, cam.extremos.der); // CREA EL GRAFO QUE USA LOS CAMINOS OBLIGATORIOS
      |         ^~~~
toll.cpp:14: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]
   14 | #define rep(i, a, b) for(int i = (a); i <= (b); i++)
      |                                         ^
toll.cpp:172:13: note: in expansion of macro 'rep'
  172 |             rep(i, 0, optimos.size() - 1){
      |             ^~~
toll.cpp:14: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]
   14 | #define rep(i, a, b) for(int i = (a); i <= (b); i++)
      |                                         ^
toll.cpp:195:13: note: in expansion of macro 'rep'
  195 |             rep(i, 0, optimos.size() - 1){
      |             ^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
18.0 / 18.0

# 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 336 KB Output is correct

Subtask #3
22.0 / 22.0

# 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 336 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct

Subtask #4
22.0 / 22.0

# 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 336 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 211 ms 8308 KB Output is correct
8 Correct 235 ms 8388 KB Output is correct
9 Correct 225 ms 8264 KB Output is correct

Subtask #5
0 / 22.0

# 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 336 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 211 ms 8308 KB Output is correct
8 Correct 235 ms 8388 KB Output is correct
9 Correct 225 ms 8264 KB Output is correct
10 Correct 2342 ms 8376 KB Output is correct
11 Execution timed out 2588 ms 8256 KB Time limit exceeded
12 Halted 0 ms 0 KB -