제출 #1169764

#제출 시각아이디문제언어결과실행 시간메모리
1169764jadai007꿈 (IOI13_dreaming)C++20
18 / 100
33 ms9292 KiB
/* Author : detective conan Problem : IOI13_dreaming Created : 14:14 UTC+7 */ #include <bits/stdc++.h> #include "dreaming.h" #define FOR(i, s, t) for(int i = s; i <= t; ++i) #define rep(i, s, t) for(int i = s; i >= t; --i) #define HAVE_TESTCASE false #define conan cin.tie(nullptr)->sync_with_stdio(false) #define mod (int)(1e9 + 7) #define vec vector #define pii pair<int, int> #define ari(n) array<int, n> #define pb push_back #define eb emplace_back #define ph push #define pf push_front #define ppb pop_back #define ppf pop_front #define ANS(n, s) cout << n << s using namespace std; using u32 = unsigned; using i64 = int64_t; using u64 = unsigned i64; const int MAX_N = 1e5 + 10; vec<pii> vc[MAX_N]; int dp[MAX_N][3], vis[MAX_N][3]; vec<int> dis; int findmax(int u){ int mx = -1, root = 0, leaf = 0; vec<int> all; queue<pii> q; q.emplace(u, 0); dp[u][0] = 0; while(!q.empty()){ int u = q.front().first, cnt = q.front().second; q.pop(); if(vis[u][0]) continue; all.pb(u); vis[u][0] = 1; dp[u][0] = cnt; if(mx < dp[u][0]) mx = dp[u][0], root = u; for(auto x:vc[u]){ int v = x.first, w = x.second; if(!vis[v][0]) q.emplace(v, cnt + w); } } mx = -1; q.emplace(root, 0); dp[root][1] = 0; while(!q.empty()){ int u = q.front().first, cnt = q.front().second; q.pop(); if(vis[u][1]) continue; vis[u][1] = 1; dp[u][1] = cnt; if(mx < dp[u][1]) mx = dp[u][1], leaf = u; for(auto x:vc[u]){ int v = x.first, w = x.second; if(!vis[v][1]) q.emplace(v, cnt + w); } } q.emplace(leaf, 0); dp[leaf][2] = 0; while(!q.empty()){ int u = q.front().first, cnt = q.front().second; q.pop(); if(vis[u][2]) continue; vis[u][2] = 1; dp[u][2] = cnt; for(auto x:vc[u]){ int v = x.first, w = x.second; if(!vis[v][2]) q.emplace(v, w + cnt); } } mx = 1e9; for(auto u:all) mx = min(mx, max(dp[u][1], dp[u][2])); return mx; } int travelTime(int N, int M, int L, int A[], int B[], int T[]){ FOR(i, 0, M - 1) vc[A[i]].eb(B[i], T[i]), vc[B[i]].eb(A[i], T[i]); FOR(i, 0, N - 1) if(!vis[i][0]) dis.pb(findmax(i)); sort(dis.begin(), dis.end(), greater<int>()); if(dis.size() == 1) return dis[2]; else if(dis.size() == 2) return dis[0] + dis[1] + L; else return max(dis[0] + dis[1] + L, dis[1] + dis[2] + 2*L); } /* int32_t main() { conan; int N, M, L, i; int res; cin >> N >> M >> L; for (i = 0; i < M; i++) cin >> A[i] >> B[i] >> T[i]; int answer = travelTime(N, M, L, A, B, T); cout << answer; 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...