제출 #920080

#제출 시각아이디문제언어결과실행 시간메모리
920080Juanchoki꿈 (IOI13_dreaming)C++14
47 / 100
187 ms51396 KiB
#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;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...