Submission #897769

#TimeUsernameProblemLanguageResultExecution timeMemory
897769aqxaDreaming (IOI13_dreaming)C++17
100 / 100
88 ms34556 KiB
#include <bits/stdc++.h> using namespace std; #include "dreaming.h" using ll = long long; // #define int ll const int N = 1e5; #define fs first #define sc second #define mp make_pair vector<pair<int, int>> g[N]; int vis[N], mxd[N], mx[N]; multiset<int> ms[N]; void dfs(int x, int p) { vis[x] = 1; for (auto [u, w]: g[x]) { if (u != p) { dfs(u, x); mxd[x] = max(mxd[x], mxd[u] + w); } } } void dfs2(int x, int p, int f) { ms[x].insert(f); for (auto [u, w]: g[x]) { if (u != p) { ms[x].insert(mxd[u] + w); } } mx[x] = *(ms[x].rbegin()); for (auto [u, w]: g[x]) { if (u != p) { ms[x].erase(ms[x].lower_bound(mxd[u] + w)); dfs2(u, x, *(ms[x].rbegin()) + w); ms[x].insert(mxd[u] + w); } } } int dfs3(int x, int p) { int res = mx[x]; for (auto [u, w]: g[x]) { if (u == p) continue; res = min(res, dfs3(u, x)); } return res; } int travelTime(int n, int m, int l, int u[], int v[], int t[]){ for (int i = 0; i < n; ++i) { vis[i] = 0; mxd[i] = 0; mx[i] = 0; } for (int i = 0; i < m; ++i) { g[u[i]].push_back(mp(v[i], t[i])); g[v[i]].push_back(mp(u[i], t[i])); } int ok = 1; vector<int> mxdist; for (int i = 0; i < n; ++i) { if (!vis[i]) { dfs(i, -1); dfs2(i, -1, 0); mxdist.push_back(dfs3(i, -1)); } ok &= (int) g[i].size() <= 1; } sort(mxdist.begin(), mxdist.end()); int ans = 0; for (int i = 0; i < n; ++i) { ans = max(ans, mx[i]); } int sz = (int) mxdist.size(); assert(sz > 0); if (sz == 1) { assert(m + 1 == n); } else { ans = max(ans, mxdist[sz - 1] + mxdist[sz - 2] + l); for (int i = 0; i < sz - 2; ++i) { ans = max(ans, mxdist[sz - 2] + mxdist[i] + l + l); } } return ans; } // int32_t main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // int nn = 4, M = 2, L = 2; // int A[]{1, 0};//{0,8,2,5,5,1,1,10}; // int B[]{2, 4};//{8,2,7,11,1,3,9,6}; // int C[]{1000, 2000};//{4,2,4,3,7,1,5,3}; // cout << "answer: " << travelTime(nn, M, L, A, B, C); // return 0; // }
#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...