Submission #1242367

#TimeUsernameProblemLanguageResultExecution timeMemory
1242367AMel0nDreaming (IOI13_dreaming)C++20
100 / 100
68 ms22840 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,N) for(ll i = 0; i < N; i++) #define all(x) (x).begin(), (x).end() #define F first #define S second #include "dreaming.h" ll N, M, L; vector<vector<pair<ll,ll>>> adj; vector<signed char> vis; pair<ll,ll> mxDist(ll n, ll p, ll d) { vis[n] = 1; pair<ll,ll> ans = {d, n}; // furthest dist, furthest node for(pair<ll,ll> c: adj[n]) { if (c.F == p) continue; pair<ll,ll> ret = mxDist(c.F, n, d + c.S); if (ret.F > ans.F) ans = ret; } return ans; } signed char rad(ll n, ll p, ll d, ll e, unordered_set<ll> &dist) { if (n == e) return 1; signed char found = 0; for(pair<ll,ll> c: adj[n]) { if (c.F == p) continue; if (rad(c.F, n, d + c.S, e, dist) == 1) found = 1; } if (found) dist.insert(d); return found; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { ::N = N, ::M = M, ::L = L; adj.resize(N); vis.resize(N); FOR(i, M) { adj[A[i]].push_back({B[i], T[i]}); adj[B[i]].push_back({A[i], T[i]}); } ll res = 0; vector<ll> radii; // let optimal node = node in a tree that best splits the diameter in half // let radii = maximum distance from any node in a tree to optimal node FOR(i, N) { if (vis[i]) continue; ll startp = mxDist(i, -1, 0).S; auto [diam, endp] = mxDist(startp, -1, 0); res = max(res, diam); unordered_set<ll> dist; rad(startp, -1, 0, endp, dist); ll minrad = 1e18; for(ll d: dist) minrad = min(minrad, max(d, diam - d)); if (minrad == 1e18) radii.push_back(0); else radii.push_back(minrad); } sort(all(radii)); reverse(all(radii)); // connect tree with the largest radii to all other trees (via respective optimal nodes) if ((ll)radii.size() >= 2) res = max(radii[0] + radii[1] + L, res); if ((ll)radii.size() >= 3) res = max(radii[1] + radii[2] + L*2, res); return (int)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...