Submission #1073977

#TimeUsernameProblemLanguageResultExecution timeMemory
1073977IgnutDreaming (IOI13_dreaming)C++17
0 / 100
70 ms14284 KiB
// Ignut #include <bits/stdc++.h> #include "dreaming.h" using namespace std; using ll = long long; const int INF = 1e9 + 123; const int MAXN = 1e5 + 123; vector<pair<int, int>> tree[MAXN]; int dist[MAXN]; void dfs(int v, int par, int d) { dist[v] = d; for (auto [to, w] : tree[v]) if (to != par) dfs(to, v, d + w); } void FindDist(int source) { dfs(source, -1, 0); } bool used[MAXN]; vector<int> comp; void dfs0(int v, int par = -1) { used[v] = true; comp.push_back(v); for (auto [to, w] : tree[v]) if (to != par) dfs0(to, v); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for (int i = 0; i < N; i ++) { tree[i].clear(); used[i] = false; } for (int i = 0; i < M; i ++) { tree[A[i]].push_back({B[i], T[i]}); tree[B[i]].push_back({A[i], T[i]}); } vector<int> c; for (int i = 0; i < N; i ++) { if (used[i]) continue; comp.clear(); dfs0(i); map<int, int> d1; for (int v : comp) d1[v] = dist[v]; int j = i; for (int v : comp) if (dist[v] > dist[j]) j = v; int ctr = i, maxDist = INF; for (int v : comp) { int d = max(d1[v], dist[v]); if (d < maxDist) { ctr = v; maxDist = d; } } c.push_back(ctr); } if (c.size() == 2) { tree[c[0]].push_back({c[1], L}); tree[c[1]].push_back({c[0], L}); } int res = 0; FindDist(0); int j = 0; for (int i = 0; i < N; i ++) if (dist[i] > dist[j]) j = i; FindDist(j); for (int i = 0; i < N; i ++) res = max(res, dist[i]); return res; }
#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...