Submission #1231454

#TimeUsernameProblemLanguageResultExecution timeMemory
1231454rhm_ganDreaming (IOI13_dreaming)C++20
47 / 100
1097 ms33528 KiB
#include <bits/stdc++.h> #include "dreaming.h" using namespace std; const int N = 1e5; struct Graph { vector<vector<pair<int, int>>> g; vector<int> dp1, dp2, res; vector<array<int, 3>> edges; int x, cnt; Graph() { g.resize(N); dp1.resize(N); dp2.resize(N); res.resize(N); x = cnt = 0; } void add(int a, int b, int w) { x = a; g[a].push_back({b, w}); g[b].push_back({a, w}); edges.push_back({a, b, w}); cnt++; } void dfs1(int u, int p) { for (auto [v, w] : g[u]) { if (v == p) continue; dfs1(v, u); if (dp1[v] + w >= dp1[u]) { dp2[u] = dp1[u]; dp1[u] = dp1[v] + w; } else { dp2[u] = max(dp2[u], dp1[v] + w); } } res[u] = max(res[u], dp1[u]); } void dfs2(int u, int p, int d) { res[u] = max(res[u], d); for (auto [v, w] : g[u]) { if (v == p) continue; int k = 0; if (dp1[v] + w == dp1[u]) { k = dp2[u]; } else { k = dp1[u]; } dfs2(v, u, max(k, d) + w); } } int findmin() { dfs1(x, -1); dfs2(x, -1, 0); int mn = 1e9; for (int i = 0; i < N; i++) { if (res[i] != 0) { mn = min(mn, res[i]); } } for (int i = 0; i < N; i++) { if (res[i] == mn) { return i; } } return 0; } void clear() { g.assign(N, vector<pair<int, int>>()); dp1.assign(N, 0); dp2.assign(N, 0); res.assign(N, 0); x = cnt = 0; } }; vector<pair<int, int>> adj[N]; Graph tmp; bool vis[N]; void dfs(int u) { vis[u] = 1; for (auto [v, w] : adj[u]) { if (!vis[v]) { tmp.add(u, v, w); dfs(v); } } } int travelTime(int n, int m, int l, int a[], int b[], int t[]) { Graph res; vector<bool> is(n); for (int i = 0; i < m; i++) { int u = a[i], v = b[i], w = t[i]; is[u] = is[v] = 1; adj[u].push_back({v, w}); adj[v].push_back({u, w}); res.add(u, v, w); } vector<int> v; for (int i = 0; i < n; i++) { if (!is[i]) { v.push_back(i); } } for (int i = 0; i < n; i++) { if (!vis[i] && is[i]) { tmp.clear(); dfs(i); v.push_back(tmp.findmin()); } } for (int i = 1; i < v.size(); i++) { res.add(v[i], v[i - 1], l); } int id = res.findmin(); int ans = 0; for (int i = 0; i < N; i++) { ans = max(ans, res.res[i]); } 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...