oj.uz

Submission #917912

# Submission time Handle Problem Language Result Execution time Memory
917912 2024-01-29T05:07:39 Z Juanchoki Dreaming (IOI13_dreaming) C++14
14 / 100
 93 ms 28856 KB 
#include"dreaming.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
    long long u, w;
};
struct tpos
{
    long long nodo, dist, padre;
};
vector<vector<edge>> adj;
pair<long long, long long> bfs (long long nodo, long long N)
{
  //  cout << "nodo: " << nodo << '\n';
        pair<long long, long long> 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;
}
long long Diametro (long long N)
{
    long long ve = bfs(0, N).first;
    return bfs(ve, N).second;
}
struct dsu
{
    struct componente
    {
        long long representante;
        long long inicio_diametro, fin_diametro;
        long long punto_medio, distancia_punto_medio;
        vector <long long> miembros;
        long long diametro;
        map<long long, long long> distancia_diametro;
        pair<long long, long long> other_bfs (long long nodo, bool pasada)
        {
            pair<long long, long long> ret;
            ret.second = -1;
            queue<tpos> q; 
            q.push({nodo, 0, -1});
            tpos temp_tpos;
            while (!q.empty())
            {
                temp_tpos = q.front(); q.pop();
                if (pasada)
                    distancia_diametro[temp_tpos.nodo] = temp_tpos.dist;
                
                for (edge e: adj[temp_tpos.nodo])
                {
                    if (e.u == temp_tpos.padre) 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 ()
        {
            long long mini = 1<<30;
            for (long long i = 0; i < miembros.size(); i++)
            {
                long long temp_dist = distancia_diametro[miembros[i]];
              //  cout << miembros[i] << " -> " << temp_dist << '\n';
                long long temp_longlong = max(temp_dist, diametro - temp_dist);
                if (mini > temp_longlong)
                {
                    mini = temp_longlong;
                    punto_medio = miembros[i];
                }
                distancia_punto_medio = mini;
            }
        }

        void get_diametro()
        {   
            if (miembros.size() > 1)  
            {
                long long resp = other_bfs(representante, 0).first;
                inicio_diametro = resp;
                pair<long long, long long> temp_pair = other_bfs(resp, 1);
                fin_diametro = temp_pair.first;
                diametro = temp_pair.second;            
            }
            else
            {   
                diametro = 0;
                distancia_diametro[miembros[0]] = 0;
                inicio_diametro = miembros[0];
                fin_diametro = miembros[0];
            } 
       //     cout << representante << ": \n";
            get_punto_medio();
        }
    };

    long long N;
    vector<long long>parent;
    vector<componente> arboles;
    vector<vector<long long>> miembros_de_componente;
    dsu(long long n)
    {
        parent.resize(n);
        N = n;
        miembros_de_componente.resize(n);
        for (long long i = 0; i < N; i++)
            parent[i] = i;
    }
    void une (long long a, long long b) 
    {
        parent[busca(a)] = busca(b);
    }
    long long busca (long long a)
    {
        if (parent[a] == a) return a;
        return (parent[a] = busca(parent[a]));
    }
    void crea_componentes()
    {
        for (long long i = 0; i < N; i++)
            miembros_de_componente[busca(i)].push_back(i);

        for (long long 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';
    adj.resize(N);
    edge temp_edge;
    dsu bosque(N);
    for (long long 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();
    long long temp_mid_pnt;
    long long cnt = 1;
    vector<long long> mid_points;
    for (dsu::componente c: bosque.arboles)
        mid_points.push_back(c.punto_medio);
    
 //   cout << '\n';
    
    for (long long i = 1; i < mid_points.size(); i++)
    {
        edge temp_edge; 
        temp_edge.u = mid_points[i-1];
        temp_edge.w = L;
        adj[mid_points[i]].push_back(temp_edge);
        temp_edge.u = mid_points[i];
        adj[mid_points[i-1]].push_back(temp_edge);
    }

  /*  for (long long i = 0; i < N; i++)
    {
        cout << i << ": ";
        for (edge e: adj[i])    
            cout << e.u << " ";
        cout << '\n';
    }
    */
    return Diametro(N);
}

Compilation message

dreaming.cpp: In member function 'void dsu::componente::get_punto_medio()':
dreaming.cpp:87:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for (long long i = 0; i < miembros.size(); i++)
      |                                   ~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:187:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for (long long i = 1; i < mid_points.size(); i++)
      |                           ~~^~~~~~~~~~~~~~~~~~~
dreaming.cpp:179:15: warning: unused variable 'temp_mid_pnt' [-Wunused-variable]
  179 |     long long temp_mid_pnt;
      |               ^~~~~~~~~~~~
dreaming.cpp:180:15: warning: unused variable 'cnt' [-Wunused-variable]
  180 |     long long cnt = 1;
      |               ^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 24568 KB Output is correct
2 Correct 93 ms 24828 KB Output is correct
3 Correct 51 ms 16116 KB Output is correct
4 Correct 13 ms 3932 KB Output is correct
5 Correct 8 ms 2652 KB Output is correct
6 Correct 18 ms 5692 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 34 ms 9812 KB Output is correct
9 Correct 45 ms 13044 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 74 ms 17328 KB Output is correct
12 Correct 85 ms 20964 KB Output is correct
13 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 24568 KB Output is correct
2 Correct 93 ms 24828 KB Output is correct
3 Correct 51 ms 16116 KB Output is correct
4 Correct 13 ms 3932 KB Output is correct
5 Correct 8 ms 2652 KB Output is correct
6 Correct 18 ms 5692 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 34 ms 9812 KB Output is correct
9 Correct 45 ms 13044 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 74 ms 17328 KB Output is correct
12 Correct 85 ms 20964 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 28856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 24568 KB Output is correct
2 Correct 93 ms 24828 KB Output is correct
3 Correct 51 ms 16116 KB Output is correct
4 Correct 13 ms 3932 KB Output is correct
5 Correct 8 ms 2652 KB Output is correct
6 Correct 18 ms 5692 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 34 ms 9812 KB Output is correct
9 Correct 45 ms 13044 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 74 ms 17328 KB Output is correct
12 Correct 85 ms 20964 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 1 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -