제출 #1209787

#제출 시각아이디문제언어결과실행 시간메모리
1209787LIA꿈 (IOI13_dreaming)C++17
0 / 100
58 ms8512 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef tuple<ll, ll, ll> plll; typedef vector<plll> vplll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; typedef vector<vector<pll>> vvpll; typedef vector<vector<ll>> vvll; typedef vector<bool> vb; const ll inf = 1e9 + 7; vvpll g; ll sum1 = 0, sum2 = 0; ll max_to_node_1 = inf, max_to_node_2 = inf; vb vis; void dfs_1(ll node, ll) { stack<ll> st; st.push(node); vis[node] = true; while (!st.empty()) { ll u = st.top(); st.pop(); for (auto [v, w] : g[u]) { if (!vis[v]) { vis[v] = true; sum1 += w; st.push(v); } } } } void dfs_2(ll node, ll) { stack<ll> st; st.push(node); vis[node] = true; while (!st.empty()) { ll u = st.top(); st.pop(); for (auto [v, w] : g[u]) { if (!vis[v]) { vis[v] = true; sum2 += w; st.push(v); } } } } void calc1(ll node, ll) { stack<pair<ll,ll>> st; st.push({node,0}); vis[node] = true; while (!st.empty()) { auto [u, d] = st.top(); st.pop(); ll mx = max(d, sum1 - d); max_to_node_1 = min(max_to_node_1, mx); for (auto [v, w] : g[u]) { if (!vis[v]) { vis[v] = true; st.push({v, d + w}); } } } } void calc2(ll node, ll) { stack<pair<ll,ll>> st; st.push({node,0}); vis[node] = true; while (!st.empty()) { auto [u, d] = st.top(); st.pop(); ll mx = max(d, sum2 - d); max_to_node_2 = min(max_to_node_2, mx); for (auto [v, w] : g[u]) { if (!vis[v]) { vis[v] = true; st.push({v, d + w}); } } } } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { g.clear(); g.resize(n); vll deg(n); 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]}); deg[A[i]]++; deg[B[i]]++; } vis.assign(n, false); for (int i = 0; i < n; ++i) if (!vis[i]) { dfs_1(i,0); break; } for (int i = 0; i < n; ++i) if (!vis[i]) { dfs_2(i,0); break; } vis.assign(n, false); for (int i = 0; i < n; ++i) if (deg[i] == 1 && !vis[i]) { calc1(i,0); break; } for (int i = 0; i < n; ++i) if (deg[i] == 1 && !vis[i]) { calc2(i,0); break; } ll ans = max({sum1, sum2, max_to_node_1 + max_to_node_2 + l}); return ans; }
#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...