Submission #1040666

#TimeUsernameProblemLanguageResultExecution timeMemory
1040666inkvizytorDreaming (IOI13_dreaming)C++17
0 / 100
21 ms11856 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; vector<int> spoj; vector<vector<pair<int, int>>> g; vector<int> maxodl1; vector<int> maxodl2; vector<int> sr; vector<int> srdl; vector<bool> odw; vector<bool> odws; int maxsr = 0; void dfs (int v) { for (auto u : g[v]) { if (!spoj[u.first]) { spoj[u.first] = spoj[v]; dfs(u.first); if (maxodl1[v] < maxodl1[u.first]+u.second) { maxodl2[v] = maxodl1[v]; maxodl1[v] = maxodl1[u.first]+u.second; } else { maxodl2[v] = max(maxodl2[v], maxodl1[u.first]+u.second); } } } } int odlg = 0; void zsr (int v) { int x = v; srdl[spoj[x]] = maxodl1[x]; while (true) { bool b = 0; for (auto u : g[x]) { if (odw[u.first]) { continue; } odw[u.first] = 1; if (maxodl1[x] == maxodl1[u.first]+u.second && max(max(maxodl2[x], odlg)+u.second, maxodl1[u.first]) < srdl[spoj[v]]) { odlg = max(maxodl2[x], odlg)+u.second; srdl[spoj[v]] = max(maxodl1[u.first], odlg); x = u.first; b = 1; break; } } if (!b) { break; } } maxsr = max(maxsr, maxodl1[x]+max(srdl[spoj[v]], maxodl2[x])); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { g.resize(N); for (int i = 0; i < M; i++) { g[A[i]].push_back({B[i], T[i]}); g[B[i]].push_back({A[i], T[i]}); } spoj.resize(N, 0); maxodl1.resize(N, 0); maxodl2.resize(N, 0); int nspoj = 1; for (int i = 0; i < N; i++) { if (!spoj[i]) { spoj[i] = nspoj; nspoj++; dfs(i); } } sr.resize(nspoj, 0); srdl.resize(nspoj, 0); odw.resize(N, 0); odws.resize(nspoj, 0); for (int i = 0; i < N; i++) { if (!odws[spoj[i]]) { odlg = 0; odw[i] = 1; odws[spoj[i]] = 1; zsr(i); } } int max1 = 0, max2 = 0, max3 = 0; for (int i : srdl) { if (i > max1) { max3 = max2; max2 = max1; max1 = i; } else if (i > max2) { max3 = max2; max2 = i; } else { max3 = max(max3, i); } } if (M == N-1) { return maxsr; } else if (M == N-2) { return max(maxsr, max1+max2+L); } return max(max(maxsr, max1+max2+L) ,max2+max3+2*L); }
#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...