Submission #897746

#TimeUsernameProblemLanguageResultExecution timeMemory
897746aqxaDreaming (IOI13_dreaming)C++17
47 / 100
120 ms34644 KiB
#include <bits/stdc++.h> using namespace std; #include "dreaming.h" using ll = long long; 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])); } 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)); } } 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(); if (sz == 1) { assert(m + 1 == n); } else { ans = max(ans, mxdist[sz - 1] + mxdist[sz - 2] + l); } // for (int i = 0; i < n; ++i) { // cout << "! " << i << ' ' << mx[i] << '\n'; // } return ans; } // int32_t main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // int N = 12, M = 8, L = 2; // int A[]{0,8,2,5,5,1,1,10}; // int B[]{8,2,7,11,1,3,9,6}; // int C[]{4,2,4,3,7,1,5,3}; // cout << "answer: " << travelTime(N, 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...