Submission #1209786

#TimeUsernameProblemLanguageResultExecution timeMemory
1209786LIADreaming (IOI13_dreaming)C++17
0 / 100
62 ms13320 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; typedef vector<vector<bool>> vvb; #define loop(i, s, e) for (ll i = (s); i < (e); ++i) #define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i) #define all(a) a.begin(), a.end() 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 d) { vis[node] = 1; for (auto [it, dis] : g[node]) { if (!vis[it]) { sum1+=dis; dfs_1(it, d+dis); } } } void dfs_2(ll node , ll d) { vis[node] = 1; for (auto [it, dis] : g[node]) { if (!vis[it]) { sum2+=dis; dfs_2(it, d+dis); } } } void calc1(ll node, ll d ) { vis[node] = 1; ll mx_for_me = max(d, sum1-d); max_to_node_1 = min( max_to_node_1, mx_for_me); for (auto [it, dis] : g[node]) { if (!vis[it]) { calc1(it, dis+d); } } } void calc2(ll node, ll d ) { vis[node] = 1; ll mx_for_me = max(d, sum2-d); max_to_node_2 = min( max_to_node_2, mx_for_me); for (auto [it, dis] : g[node]) { if (!vis[it]) { calc2(it, dis+d); } } } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { g.resize(n); vll dar(n); loop(i,0,m) { g[A[i]].push_back({B[i], T[i]}); g[B[i]].push_back({A[i], T[i]}); dar[A[i]]++; dar[B[i]]++; } vis.assign(n, false); loop(i,0,n) { if (!vis[i]) { dfs_1(i,0); break; } } loop(i,0,n) { if (!vis[i]) { dfs_2(i,0); break; } } vis.assign(n, false); loop(i,0,n) { if (dar[i] == 1 && !vis[i]) { calc1(i,0); break; } } loop(i,0,n) { if (dar[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...