Hola, intenté este problema: es la C del CIIC-2016, mi código sólo
resuelve el caso base :'v.
https://omegaup.com/arena/CIIC-2016#problems/don-porfirio
Me pueden ayudar con ideas para obtener 100 y el código por favor .
1 me gusta
Hola!
Adjunto el PDF de esa CIIC para referencia, cuando tenga tiempo si nadie contestó nada me pongo a mirarlo 
ExamenFinalCIIC2016.pdf (567,3 KB)
2 Me gusta
Hola, tengo una idea que creo que sirve.
Aún no lo programé así que no se que detalles podría tener la implementación.
Lo que se me ocurrió fue armar el spanning tree desde cualquier nodo.
Fijate que si tomas la arista más pesada definida como arista(a, b), los caminos que empiezan en algún nodo dentro del spanning tree del nodo b y terminan en algún nodo fuera de ese spanning tree tienen como valor el valor de arista(a, b).
Si te metes en ese spanning tree podés hacer lo mismo hasta quedarte con una sola arista. Esto podría hacerse con recursividad.
Luego de cada retorno te pueden quedar aristas por analizar así que tenés que ir tomando la arista con mayor valor no analizada todavía e ignorar los spanning trees ya usados (porque si ya analizaste un spanning tree significa que ya analizaste todos los caminos que salen de esos nodos). Cada vez que analizas una arista la podes bloquear actualizando un segment tree y de esa manera saber cuántos nodos hay en cada rango.
Espero que se haya entendido la idea. Probablemente pronto lo programe y amplíe este post. Saludos.
PD: me faltó decir que el segment tree, aparte de bloquear spanning trees usado también sirve para obtener la arista más pesada en un rango.
1 me gusta
¡Buenas!
La idea tiene elementos conducentes a una solución correcta. Está un poco confusa e incompleta: “Spanning Tree” o “Árbol Generador” se le llama a un árbol que abarca todos los nodos de un grafo. En este problema de hecho el grafo dado ya es un árbol, así que un spanning tree es el grafo entero.
Creo que cuando decís “Spanning Tree” te estás refiriendo en todo momento a “subárboles”, en los que se va descomponiendo el árbol cuando lo vas “separando en dos” por la arista de mayor valor.
Si bien la idea en sí está bien, creo que es más simple pensarlo utilizando union find. Ya que si se van insertando las aristas de menor a mayor, eso tiene una estructura muy particular, y en los caminos nuevos que habilita cada arista que se agrega, siempre está garantizado que esa arista nueva es la más pesada. Así que con un union find que pueda mantener los tamaños de las componentes, se podría resolver.
3 Me gusta
Si, tenés razón. Medio confuso como lo redacté.
Por spanning tree me refería a armar un vector con el recorrido del DFS de tal manera que los hijos de un nodo estén todos uno al lado del otro. Entonces para contar los nodos habilitados del subárbol del nodo A habría que tener un vector más con el tamaño del subárbol y se podría hacer:
segtree.query(dfs_num[A], dfs_num[A] + tamano[A]);
Espero que se haya aclarado lo que había querido decir jaja.
Probé la idea hace unos días y funciona solo hay que ser cuidadoso implementando todo 
.
2 Me gusta
Y respecto a la idea del union find realmente sí es mucho más simple jajaja no se me había ocurrido pensarlo así.
1 me gusta
Te agradezco también el tip para la idea! Yo lo estaba pensando en hacer algo con DFS, de sacar la suma tomando los máximos considerando al nodo 1 como la raíz, y así obtener la suma para todos respecto a dicho. Luego pensaba que la suma partiendo desde un nodo adyacente a dicha raíz (conectado por una arista), a partir de todas las distancias posibles desde dicho, podría calcularlo a partir de dicho valor antes obtenido para la raíz, viendo de sacar todos los hijos del adyacente, y ver de alguna forma la arista que agregué al considerar dicho nodo adyacente como partida, a cuántos otros superaba su peso y así recalcular el valor. Pero mientras más lo pensaba, más veía que eso se complicaba.
Los union-find generalmente no los quería modificar porque si no ya veía que podía romperlos, y de hecho siempre tuve la duda si podía mantener la suma de los tamaños de las componentes/conjuntos. Pero ya que me pareció muy interesante la idea de hacerlo, pude ver que era apenas 2 o 3 líneas más, jeje. Así que después de complicarme mucho con checks y otras cosas, directamente pensé que a partir de conectar las aristas según su nivel de belleza de menor a mayor como decís, para luego al terminar de agregar todas las de un mismo nivel, podría directamente agregar al resultado \frac{N*(N-1)}{2} siendo N la cantidad de elementos de una componente, ya que representaría la cantidad de pares sin repetición posibles dentro. Pero, además hago uso de una matriz ll combPerSet[MAXN] en el cual tengo la cantidad de pares por componente del union-find antes contemplados con un menor nivel de belleza, así no sumo de más, siendo así necesario en la implementación del union-find que, al unir dos conjuntos, además de sumar la cantidad de elementos de una componente en la otra, también la cantidad de pares contemplados.
Lo único raro es que mi implementación saca 80 ptos (en https://omegaup.com/arena/problem/don-porfirio/#problems/don-porfirio), diciéndome que tuve Partial Answer, sugiriendo que mi código debió haber fallado en alguna subtarea. Pero lo raro es que dada la distribución de las subtareas, ¡mi solución pasó con la cota más alta y está fallando en alguno con cota más chica! Lo único que me lleva a pensar es que hay algún caso de prueba borde que está fallando…pero ya probé varias cosas, principalmente pensando que podría dar overflow, y no logro solucionarlo.
Alguna idea de qué puede estar pasando? Dejo mi código, tanto si es útil como si alguien ve algo mal en mi implementación.
Código
#include <bits/stdc++.h>
#define forn(i,n) for(int i = 0; i < int(n); i++)
#define forsn(i,s,n) for(int i = int(s); i < int(n); i++)
#define dforn(i,n) for (int i = int(n)-1; i >= 0; i--)
#define dforsn(i,s,n) for(int i = int(n)-1; i >= int(s); i--)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fst first
#define snd second
#define FAST_IO ios::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 1e5+5;
const int INF = 2e9+5;
const int MOD = 1e9+7;
struct edges {
int a,b,w;
bool operator< (const edges &o) const {
return o.w > w;
}
};
vector<edges> G;
ll cntPerSet[MAXN], combPerSet[MAXN];
struct DS {
vi p,r;
void init(int N) {
p.assign(N+3,-1);
r.assign(N+3,-1);
}
int find(int x) {return (p[x] == -1 ? x : p[x] = find(p[x]));}
void join (int &a, int &b) {
int x = find(a), y = find(b);
if (x == y) return;
if (r[y] < r[x]) {
p[y] = x;
cntPerSet[x] += cntPerSet[y];
combPerSet[x] += combPerSet[y];
}
else {
p[x] = y;
cntPerSet[y] += cntPerSet[x];
combPerSet[y] += combPerSet[x];
if (r[y] == r[x]) r[y]++;
}
}
};
DS UF;
int main() {
FAST_IO;
int N; cin >> N;
forn (i,MAXN) cntPerSet[i] = 1;
UF.init(N);
forn (i,N-1) {
int a,b,w; cin >> a >> b >> w;
a--; b--;
G.pb({a,b,w});
}
G.pb({N+2,N+2,INF}); // dummy
sort(all(G)); // ordeno aristas por costo menor a mayor
ll weight = G[0].w, rta = 0;
set<int> Q;
forn (i,N) {
auto e = G[i];
//cerr << "OK" << ' ' << i << endl;
if (e.w > weight) {
while (not Q.empty()) {
auto x = *Q.begin(); Q.erase(Q.begin());
int meC = UF.find(x); ll cant = cntPerSet[meC];
ll comb = (cant*(cant-1))/2;
rta = ((rta + (((comb-combPerSet[x])*weight) % MOD)) % MOD);
combPerSet[x] = comb;
// cerr << UF.find(x) <<' ' << x << ' ' << cntPerSet[UF.find(x)] << ' ' << rta << ' ' << weight << ' ' << mark[x] << ' ' << conj[meC] << endl;
}
weight = e.w;
}
UF.join(e.a,e.b);
Q.insert(UF.find(e.a));
}
cout << (rta + MOD) % MOD;
return 0;
}
1 me gusta
Creo que no hay necesidad de pasarlos por referencia, solo se usa el valor.
En lugar de copy pastear el código que sigue dos veces cambiando todos los y con x, lo que es propenso a olvidarse alguno y ante cualquier cambio futuro hay que cambiar los dos así que es propenso a no cambiar uno y que queden desfasados, se puede hacer directamente algo como
if (r[y] > r[x]) swap(x,y);
// Ahora ya asumimos en lo que sigue que r[y] <= x
El cntPerSet parece ok, pero no entiendo bien qué es el combPerSet. Parecería ser lo mismo porque se suman al unirse, pero a veces se le suma y arranca en cero.
Si no entiendo mal, al poner una arista que une a con b que no estaban unidos, la cantidad de caminos que se crean que van a tener esa arista como maxima es cnt[componenteA] * cnt[componenteB], y con eso ya basta creo.
1 me gusta
Muchas gracias por la respuesta! Lo de intercambiar lo entiendo perfectamente, es que nada más había escrito de memoria la implementación de Union-Find que saqué del libro Competitive Programming 3, en el cual no hay mucha diferencia entre un swap y un if de lo corto que es esa parte, y por lo que no queda fea hacer uno o el otro. De todas formas, si queda feo cuando le agrego estas dos operaciones que estaba haciendo y se nota que podría evitar el copy-paste, justamente por ejemplo haciendo swap.
La idea del combPerSet era obtener precisamente la nueva cantidad de caminos creados después de una pasada, restando a las ya procesadas con otro peso de aristas menor. Igual tenés toda la razón, y no me di cuenta, que es mucho más sencillo simplemente multiplicar la cantidad de nodos de una componente por la del otro para obtener el mismo número. Entonces fui cambiando eso y me di cuenta de algunas errores medio pavos que tenía, como que me fijaba por precisamente combPerSet para directamente el valor del set y mientras para cntPerSet del find sobre dicho elemento, cuando se supone que ambos deberían apuntar directamente al conjunto original (el find). De todas formas, curiosamente esto no afecta al puntaje, por lo que seguí probando arreglar otras cosas.
Luego me di cuenta que como me estoy fijando por la cantidad de aristas nuevas, no es necesario esperar a que procese todas las aristas de un mismo peso, y más aún que se simplifica obtener el número con lo que puedo multiplicar cantidades entre componentes que se unen. Y esto es clave de hecho, ya que cambiando un poco el Union-Find, cuando estaba viendo de directamente hacer lo del swap, según si unía a \rightarrow b o a \leftarrow b pasaba de tener 80ptos a 60ptos. Como el comportamiento debería ser idéntico, llegué a creer que según la forma del input y mi código, unir de una forma u otra podría llevar a overflow o no (incluso más allá de haber probado pasando todo a long long sin éxito). Entonces al ir directamente sumando a la respuesta por cada join, era menos propoenso a tener overflow.
Como digo fue clave, pues después de esta corrección dio AC.
Los casos son medio raros igual, porque me esperaría un overflow en el caso más grande y no en uno de los chicos 
.
Como última aclaración, paso los valores al join del Union-Find por referencia porque tengo entendido es levemente más eficiente al no tener que copiarlos.
Bueno, nuevamente muchas gracias por la respuesta y haberme ayudado a resolver el problema! 
Dejo mi código si a alguien le viene útil:
Código AC
#include <bits/stdc++.h>
#define forn(i,n) for(int i = 0; i < int(n); i++)
#define forsn(i,s,n) for(int i = int(s); i < int(n); i++)
#define dforn(i,n) for (int i = int(n)-1; i >= 0; i--)
#define dforsn(i,s,n) for(int i = int(n)-1; i >= int(s); i--)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fst first
#define snd second
#define FAST_IO ios::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 1e5+5;
const int INF = 2e9+5;
const int MOD = 1e9+7;
struct edges {
int a,b,w;
bool operator< (const edges &o) const {
return o.w > w;
}
};
edges G[MAXN];
ll cntPerSet[MAXN];
struct DS {
vi p,r;
void init(int N) {
p.assign(N+3,-1);
r.assign(N+3,-1);
}
int find(int x) {return (p[x] == -1 ? x : p[x] = find(p[x]));}
ll join (int &a, int &b) {
int x = find(a), y = find(b);
if (x == y) return 0;
ll val = cntPerSet[y]*cntPerSet[x];
if (r[x] < r[y]) swap(x,y);
p[y] = x; cntPerSet[x] += cntPerSet[y];
if (r[y] == r[x]) r[x]++;
return val;
}
};
DS UF;
int main() {
//FAST_IO;
int N; scanf("%d",&N);
forn (i,MAXN) cntPerSet[i] = 1;
UF.init(N);
forn (i,N-1) {
int a,b,w; scanf("%d %d %d",&a,&b,&w);
a--; b--;
G[i] = {a,b,w};
}
sort(G,G+N-1); // ordeno aristas por costo menor a mayor
ll rta = 0;
forn (i,N-1) {
auto e = G[i];
ll newComb = UF.join(e.a,e.b);
rta = ((rta + (((newComb % MOD)*e.w) % MOD)) % MOD);
}
printf("%lld",((rta + MOD) % MOD));
return 0;
}
¡De nada!
Pasar por referencia solamente es relevante para la eficiencia con estructuras grandes (vectors, maps, queues, etc, y structs que los contengan), ya que copiar esos implica copiar mucha memoria. En el caso de tipos enteros/bool/char/primitivos, no cambia, ya que igual al pasar por referencia por dentro se copia el puntero (dirección de memoria de la variable referenciada), que mide 32 bits o 64 bits. Puede empeorar la performance incluso al hacer más indirecciones o cómputos más raros, pero lo más probable es que sea simplemente irrelevante en estos casos.
Recomendaría usar la siguiente regla para los pasajes por referencia:
- Si la variable es algo que se escribe intencionalmente desde dentro de la función como parte del funcionamiento, debe ir por referencia para poder modificarla.
- Si no, solamente pasar por referencia las estructuras grandes, para evitar copiarlas. En ese caso siempre que sea posible pasarlas como const vector & por ejemplo, con el const, para evitar modificarlas por error. Además que sea const permite algunas cosas más, como pasar una variable temporal (un rvalue / expresión / resultado de función), o usarlo en el operator < de las estructuras de stl (que en general no funciona bien si se implementa con & pero sin el const)
- En todos los demás casos pasar por valor directamente
1 me gusta
Lo tenía presente para modificar el contenido de las variables que paso por referencia por supuesto, y también con estructuras grandes. Pero tenía la idea que también hay beneficio lo suficientemente significativo como para también hacerlo con enteros o cualquier otra estructura de pocos elementos. Y el uso de const si bien lo tenía, no lo tenía tan en la cabeza y más bien lo usaba con estructuras que conocía, así que está bueno tenerlo en cuenta.
Así que muchas gracias por los tips y nuevamente por la ayuda con el problema!