Submission #337698

#TimeUsernameProblemLanguageResultExecution timeMemory
337698BlancaHMDreaming (IOI13_dreaming)C++14
0 / 100
1029 ms7792 KiB
#include <iostream> #include <vector> #include <queue> #include <algorithm> #include "dreaming.h" using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pii; typedef vector<pii> vpii; typedef vector<vpii> vvpii; pii calcDist(int i, vvpii & G, vector<bool> & visited, vi & dist1, vi & dist2) { queue<int> Q; Q.push(i); int u, v, t, N = (int) G.size(), maxNode = i; vector<int> vertices = {}; dist1[i] = 0; while(!Q.empty()) { u = Q.front(); Q.pop(); visited[u] = true; vertices.push_back(u); if (dist1[u] > dist1[maxNode]) maxNode = u; for (auto connection: G[u]) { v = connection.first; t = connection.second; if (dist1[v] > dist1[u]+t) { dist1[v] = dist1[u]+t; Q.push(v); } } } dist2.assign(N, 1e9); dist2[maxNode] = 0; Q.push(maxNode); while(!Q.empty()) { u = Q.front(); Q.pop(); if (dist2[u] > dist2[maxNode]) maxNode = u; for (auto connection: G[u]) { v = connection.first; t = connection.second; if (dist2[v] > dist2[u]+t) { dist2[v] = dist2[u]+t; Q.push(v); } } } int ecc = 0; for (auto vert: vertices) { ecc = max(ecc, min(dist1[vert], dist2[vert])); } return make_pair(ecc, dist2[maxNode]); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { vvpii G(N, vpii()); vector<bool> visited(N, false); for (int i = 0; i < M; i++) { G[A[i]].push_back(make_pair(B[i], T[i])); G[B[i]].push_back(make_pair(A[i], T[i])); } int CC = 0; vi diam = {}, ecc = {}, dist1(N, 1e9), dist2(N, 1e9); pii curCC; for (int i = 0; i < N; i++) { if (!visited[i]) { curCC = calcDist(i, G, visited, dist1, dist2); ecc.push_back(curCC.first); diam.push_back(curCC.second); CC++; } } int ans = diam[0]; for (int i = 1; i < CC; i++) ans = max(ans, diam[i]); sort(ecc.begin(), ecc.end(), greater<int>()); for (int i = 1; i < CC; i++) ans = max(ans, ecc[i]+ecc[0]+L); return ans; }
#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...