제출 #674258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674258		a_aguilo	꿈 (IOI13_dreaming)	C++14	100 / 100	137 ms	24132 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>

using namespace std;

int diameter;
vector<vector<int>> AdjList, Weights;
vector<int> component, father, distFather, LongestDepth, NodeForLongestDepth, SecondLongestDepth;

void dfs(int node){//Primera pasada de la dp
    //Existe el caso de que sea una hoja, así que sus máximas profundidades serían 0
    LongestDepth[node] = 0;
    SecondLongestDepth[node] = 0;
    //actualizamos máximas profundidades teniendo en cuenta los hijos del nodo
    for(int next = 0; next < AdjList[node].size(); ++next){
        int neighbour = AdjList[node][next];
        int time = Weights[node][next];
        if(neighbour == father[node]) continue;//Descartamos visitar al padre del nodo
        //El hijo es visitado por primera vez, así que hay que completar la información de su padre (este nodo)
        father[neighbour] = node;
        distFather[neighbour] = time;
        component[neighbour] = component[node];
        dfs(neighbour);//visitamos al hijo
        int DepthNeighbour = LongestDepth[neighbour] + time; //máxima profundidad obtenida si contiene al hijo del nodo
        if(DepthNeighbour >= LongestDepth[node]){
            //Si es mayor que la máxima profundidad obtenida hasta ahora, actualizamos
            SecondLongestDepth[node] = LongestDepth[node];
            LongestDepth[node] = DepthNeighbour;
            NodeForLongestDepth[node] = neighbour;
        }else if(DepthNeighbour >= SecondLongestDepth[node]){//También podría ser la segunda mayor profundidad
            SecondLongestDepth[node] = DepthNeighbour;
        }
    }
}
int getDepthComponent(int node){//segunda pasada de la dp: ahora calculamos las profundidades de 
    //manera absoluta, no respecto al subárbol de un nodo. Por eso toca tener en cuenta los 
    //caminos que salgan del nodo y pasen por su padre.
    if(father[node] != node){//Si el nodo no es la raíz que hemos usado para explorar la componente
        //porque de lo contrario ya tenemos la máxima profundidad absoluta
        int predecesor = father[node];
        int optative = 0;
        //Casos
        //  -La máxima profundidad del padre no pasa por este nodo -> probar la profundidad que obtenemos 
        //  yendo de este nodo a su padre y de allí a su máxima profundidad
        if(node != NodeForLongestDepth[predecesor]) optative = LongestDepth[predecesor]+distFather[node];
        //  -La máxima profundidad del padre pasa por este nodo -> no nos sirve, así que probar la profundidad
        //  que obtenemos yendo de este nodo a su padre y de allí a su segunda máxima profundidad
        else optative = SecondLongestDepth[predecesor]+distFather[node];
        //Actualizamos los valores de máxima profundidad y segunda máxima profundidad con respecto a la 
        //profundidad del camino que pasa por el padre
        if(optative >= LongestDepth[node]){
            SecondLongestDepth[node] = LongestDepth[node];
            LongestDepth[node] = optative;
            NodeForLongestDepth[node] = predecesor;
        }else if(optative >= SecondLongestDepth[node]) SecondLongestDepth[node] = optative;
    }
    int ans = LongestDepth[node];//Obtenemos la profundidad si tomamos este nodo como raíz
    diameter = max(diameter, ans);//Actualizamos el valor del diámetro como la máxima distancia si salimos de este nodo
    //Como pasaremos por todos los nodos de una componente acabaremos obteniendo el diámetro de esa componente en forma
    // de máxima profundidad de una hoja, y como visitamos todas las componentes obtendremos el máximo diámetro entre
    //ellas, que es otra de las posibles máximas rutas.
    for(int neighbour: AdjList[node]) {
        if(neighbour != father[node])ans = min(ans, getDepthComponent(neighbour));//Buscar la profundidad si cogemos su 
        //hijo como raíz, para el que también actualizaremos las profundidades teniendo en cuenta los caminos que pasen 
        //por su padre. Cada vez nos vamos quedando con la menor profundidad, que es lo que buscamos.
    }
    return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    //Pasamos los datos a formato de lista de adyacencia
    AdjList = vector<vector<int>>(N);
    Weights = vector<vector<int>>(N);
    for(int i = 0; i < M; ++i){
        AdjList[A[i]].push_back(B[i]);
        AdjList[B[i]].push_back(A[i]);
        Weights[B[i]].push_back(T[i]);
        Weights[A[i]].push_back(T[i]);
    }
    component = vector<int>(N, -1); // Indica la componente conexa a que pertenece cada nodo
    LongestDepth = vector<int>(N, -1); //Indica la máxima profundidad que se consigue desde cada nodo
    SecondLongestDepth = vector<int> (N, -1); //Indica el camino con segunda máxima profundidad saliendo de cada nodo
    //dicho camino es diferente del de la máxima profundidad: no comparten ninguna arista
    NodeForLongestDepth = vector<int>(N, -1); //NodeForLongestDepth[i] = j cuando j es el hijo de i mediante el que
    //se accede al camino de máxima profundidad
    distFather = vector<int>(N, 1); //Indica la distancia que cada nodo tiene con su padre si empezamos el dfs 
    //de la componente en el nodo numerado más pequeño
    father = vector<int>(N, -1); //Indica el padre de cada nodo
    vector<int> depthsComponents;//Indica la profundidad que cada componente conexa tendrá 
    // si accedemos a ella desde su centroide
    diameter = 0; //La máxima distancia para atravesar el grafo también puede ser el diámetro de una de las componentes
    for(int i = 0; i < N; ++i){
        if(component[i] == -1){//Si no ha sido visitado al formar una componente
            component[i] = i; //Creamos nueva componente
            //Este nodo es raíz para explorar la componente, por lo que es su mismo padre
            distFather[i] = 0;
            father[i] = i;
            dfs(i);//Primera pasada de la dp -> Se calculan las profundidades usando la raíz como referencia
            depthsComponents.push_back(getDepthComponent(i));//Segunda pasada de la dp para que ahora las profundidades 
            //sean en general. Añadimos a la lista de profundidades de las componentes 
            //la profundidad de la componente que venimos de explorar si tomamos como raíz el centroide
        }
    }
    sort(depthsComponents.rbegin(), depthsComponents.rend()); //Ordenamos la lista de profundidades de mayor a menor
    //Posibles casos
    //  -La máxima ruta es uno de los diámetros -> Número de componentes >= 1
    //      -> esto se ha ido calculando haciendo el máximo en la variable diameter
    //  -La máxima ruta es L + la mayor profundidad + la segunda mayor profundidad -> Número de componentes >= 2
    //  -La máxima ruta es 2*L + la segunda mayor profundidad + la tercera mayor profundidad -> Número de componentes >= 3
    if(M == N-1) return diameter;
    int MaxTravel = max(diameter, depthsComponents[0] + depthsComponents[1] + L);
    if((N-M-1) == 1) return MaxTravel;
    MaxTravel= max(MaxTravel, depthsComponents[1] + depthsComponents[2] + 2*L);
    return MaxTravel;
}

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:15:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int next = 0; next < AdjList[node].size(); ++next){
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23