Submission #1231644

#TimeUsernameProblemLanguageResultExecution timeMemory
1231644rhm_ganDreaming (IOI13_dreaming)C++20
14 / 100
1095 ms22896 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; int x; vector<int> node; vector<array<int, 3>> edges; Graph() { g.resize(N); dp1.resize(N); dp2.resize(N); res.resize(N); x = 0; } void add(int a, int b, int w) { if (g[a].empty()) node.push_back(a); if (g[b].empty()) node.push_back(b); x = a; g[a].push_back({b, w}); g[b].push_back({a, w}); edges.push_back({a, b, w}); } void dfs1(int u, int p) { dp1[u] = dp2[u] = 0; 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); } } void process() { dfs1(x, -1); dfs2(x, -1, 0); } int findmin() { process(); int mn = 1e9; for (auto u : node) { mn = min(mn, res[u]); } for (auto u : node) { if (res[u] == mn) { return u; } } return 0; } void clear() { for (auto u : node) { g[u].clear(); dp1[u] = dp2[u] = res[u] = 0; } node.clear(); edges.clear(); x = 0; } }; vector<pair<int, int>> adj[N]; Graph tmp; Graph res; bool first = 1; bool vis[N]; void dfs(int u) { vis[u] = 1; for (auto [v, w] : adj[u]) { if (!vis[v]) { if (first) { res.add(u, v, w); } else { tmp.add(u, v, w); } dfs(v); } } } int travelTime(int n, int m, int l, int a[], int b[], int t[]) { 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}); } for (int i = 0; i < n; i++) { if (!vis[i] && is[i]) { tmp.clear(); dfs(i); if (!first) { res.add(res.findmin(), tmp.findmin(), l); for (auto [u, v, w] : tmp.edges) { res.add(u, v, w); } } first = 0; } } vector<int> v; for (int i = 0; i < n; i++) { if (!is[i]) { int x = res.findmin(); res.add(x, i, l); } } res.process(); 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...