제출 #855381

#제출 시각아이디문제언어결과실행 시간메모리
855381tvladm2009Dreaming (IOI13_dreaming)C++17
100 / 100
66 ms24916 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = (int) 1e5 + 7; const int INF = (int) 2e9; int dep[N], up[N]; bool vis[N]; vector<pair<int, int>> g[N]; int n, m, l; int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n = N; m = M; l = L; 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]}); } int diam, mx_dist; function<void(int)> dfs1 = [&] (int a) { vector<pair<int, int>> gg; vis[a] = 1; for (auto &b : g[a]) { if (!vis[b.first]) { gg.push_back(b); dfs1(b.first); diam = max(diam, dep[a] + dep[b.first] + b.second); dep[a] = max(dep[a], dep[b.first] + b.second); } } g[a] = gg; }; function<void(int)> dfs2 = [&] (int a) { mx_dist = min(mx_dist, max(up[a], dep[a])); for (int it = 0; it < 2; it++) { int r = 0; for (auto &b : g[a]) { up[b.first] = max(up[b.first], up[a] + b.second); up[b.first] = max(up[b.first], r + b.second); r = max(r, dep[b.first] + b.second); } reverse(g[a].begin(), g[a].end()); } for (auto &b : g[a]) { dfs2(b.first); } }; vector<int> guys; int sol = 0; for (int r = 0; r < n; r++) { if (!vis[r]) { diam = 0; mx_dist = INF; dfs1(r); dfs2(r); guys.push_back(mx_dist); sol = max(sol, diam); } } sort(guys.rbegin(), guys.rend()); if ((int) guys.size() >= 2) { sol = max(sol, guys[0] + guys[1] + l); } if ((int) guys.size() >= 3) { sol = max(sol, guys[1] + guys[2] + 2 * l); } return sol; }
#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...