제출 #920080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920080		Juanchoki	꿈 (IOI13_dreaming)	C++14	47 / 100	187 ms	51396 KiB

dreaming

#include"dreaming.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int u, w;
};
struct tpos
{
    int nodo, dist, padre;
};
int max_tam;
vector<vector<edge>> adj;
pair<int, int> bfs (int nodo, int N)
{
  //  cout << "nodo: " << nodo << '\n';
        pair<int, int> ret;
        ret.second = -1;
        queue<tpos> q; 
        q.push({nodo, 0, -1});
        tpos temp_tpos;
        vector<bool> visi(N);
        while (!q.empty())
        {
            temp_tpos = q.front(); q.pop();
            visi[temp_tpos.nodo] = 1;
            //cout << "    " << temp_tpos.nodo <<  " " << temp_tpos.dist << "\n";
            for (edge e: adj[temp_tpos.nodo])
            {
           //     cout << temp_tpos.nodo << " vecinos: " << e.u << '\n';
                if (visi[e.u]) continue;
                q.push({e.u, temp_tpos.dist+e.w, temp_tpos.nodo}); 
            }
            if (temp_tpos.dist > ret.second)
            {
                ret.second = temp_tpos.dist;
                ret.first = temp_tpos.nodo;
            }
        }
    //cout << '\n';
    return ret;
}
int Diametro (int N)
{
    int ve = bfs(0, N).first;
    return bfs(ve, N).second;
}
struct dsu
{
    struct componente
    {
        int representante;
        int inicio_diametro, fin_diametro;
        int punto_medio, distancia_punto_medio;
        vector <int> miembros;
        int diametro;
        map<int, int> distancia_diametro1, distancia_diametro2;
        void BFS (int nodo)
        {
            queue<tpos> q; 
            q.push({nodo, 0, -1});
            vector<bool> visi(max_tam);
            
            tpos temp_tpos;
            while (!q.empty())
            {
                temp_tpos = q.front(); q.pop();
                visi[temp_tpos.nodo] = 1;
                distancia_diametro2[temp_tpos.nodo] = temp_tpos.dist;
                for (edge e: adj[temp_tpos.nodo])
                {
                    if (visi[e.u]) continue;
                    q.push({e.u, temp_tpos.dist+e.w, temp_tpos.nodo}); 
                }
            }
        }
 
        pair<int, int> other_bfs (int nodo, bool pasada)
        {
            pair<int, int> ret;
            ret.second = -1;
            queue<tpos> q; 
            q.push({nodo, 0, -1});
            vector<bool> visi(max_tam);
            tpos temp_tpos;
            while (!q.empty())
            {
                temp_tpos = q.front(); q.pop();
                 visi[temp_tpos.nodo] = 1;
                if (pasada)
                    distancia_diametro1[temp_tpos.nodo] = temp_tpos.dist;
                
                for (edge e: adj[temp_tpos.nodo])
                {
                    if (visi[e.u]) continue;
                    q.push({e.u, temp_tpos.dist+e.w, temp_tpos.nodo}); 
                }
                if (temp_tpos.dist > ret.second)
                {
                    ret.second = temp_tpos.dist;
                    ret.first = temp_tpos.nodo;
                }
            }
            return ret;
        }
 
        void get_punto_medio ()
        {
            int mini = 1<<30;
            BFS(fin_diametro);
            for (int i = 0; i < miembros.size(); i++)
            {
                int temp_dist = distancia_diametro1[miembros[i]];
              //  cout << miembros[i] << " -> " << temp_dist << '\n';
                int temp_longlong = max(temp_dist, distancia_diametro2[miembros[i]]);
                if (mini > temp_longlong)
                {
                    mini = temp_longlong;
                    punto_medio = miembros[i];
                }
                distancia_punto_medio = mini;
            }
        }
 
        void get_diametro()
        {   
                int resp = other_bfs(representante, 0).first;
                inicio_diametro = resp;
                pair<int, int> temp_pair = other_bfs(resp, 1);
                fin_diametro = temp_pair.first;
                diametro = temp_pair.second;            
             
       //     cout << representante << ": \n";
                get_punto_medio();
        }
    };
 
    int N;
    vector<int>parent;
    vector<componente> arboles;
    vector<vector<int>> miembros_de_componente;
    dsu(int n)
    {
        parent.resize(n);
        N = n;
        miembros_de_componente.resize(n);
        for (int i = 0; i < N; i++)
            parent[i] = i;
    }
    void une (int a, int b) 
    {
        parent[busca(a)] = busca(b);
    }
    int busca (int a)
    {
        if (parent[a] == a) return a;
        return (parent[a] = busca(parent[a]));
    }

    void crea_componentes()
    {
        for (int i = 0; i < N; i++)
            miembros_de_componente[busca(i)].push_back(i);
 
        for (int i = 0; i < N; i++)
        {
            if (miembros_de_componente[i].empty()) continue;
            componente comp_temp;
            comp_temp.representante = i;
            comp_temp.miembros = miembros_de_componente[i];
            arboles.push_back(comp_temp);
            arboles.back().get_diametro();
            //cout << '\n';
        }
        
    }
};
 
int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
  //  cout << '\n';
    max_tam = N;
    adj.resize(N);
    edge temp_edge;
    dsu bosque(N);
    for (int i = 0; i < M; i++)
    {
        temp_edge.u = B[i];
        temp_edge.w = T[i];
        adj[A[i]].push_back(temp_edge);
        temp_edge.u = A[i];
        adj[B[i]].push_back(temp_edge);
        bosque.une(A[i], B[i]);
    }
    bosque.crea_componentes();
    int temp_mid_pnt;
    int cnt = 1;
    vector<dsu::componente> vector_componentes;
    for (dsu::componente comp: bosque.arboles)
        vector_componentes.push_back(comp);

    for (int i = 1; i < vector_componentes.size(); i++)
    {
        dsu::componente comp = vector_componentes[i], sig = vector_componentes[i-1];
        adj[comp.punto_medio].push_back({sig.punto_medio, L});
        adj[sig.punto_medio].push_back({comp.punto_medio, L});
        bosque.une(comp.punto_medio, sig.punto_medio);
        int temp_int = min (max (comp.distancia_punto_medio+L, sig.distancia_punto_medio+L), max(comp.distancia_punto_medio, sig.distancia_punto_medio+L));
        vector_componentes[i].distancia_punto_medio = temp_int;
        vector_componentes[i].diametro = max (comp.diametro, max (sig.diametro, comp.distancia_punto_medio + sig.distancia_punto_medio + L));
    }
   // bosque.crea_componentes();

    return vector_componentes.back().diametro;
}

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

dreaming.cpp: In member function 'void dsu::componente::get_punto_medio()':
dreaming.cpp:111:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for (int i = 0; i < miembros.size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:202:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<dsu::componente>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |     for (int i = 1; i < vector_componentes.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:196:9: warning: unused variable 'temp_mid_pnt' [-Wunused-variable]
  196 |     int temp_mid_pnt;
      |         ^~~~~~~~~~~~
dreaming.cpp:197:9: warning: unused variable 'cnt' [-Wunused-variable]
  197 |     int cnt = 1;
      |         ^~~

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