Submission #203644

#TimeUsernameProblemLanguageResultExecution timeMemory
203644osaaateiasavtnlOlympic Bus (JOI20_ho_t4)C++14
100 / 100
166 ms35612 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcount #define ll long long #define mp make_pair #define f first #define s second #define Time (double)clock()/CLOCKS_PER_SEC const int N = 1e5 + 7, INF = 1e18 + 7; struct Edge { int u, v, c, d; } e[N]; struct Ed { int v, c, i; }; int n, m; int dist1[N], par1[N], par_ed1[N], sec1[N], best1[N]; int distn[N], parn[N], par_edn[N], secn[N], bestn[N]; int tmp[N]; int dist1_rev[N], sec1_rev[N], best1_rev[N];; int distn_rev[N], secn_rev[N], bestn_rev[N]; vector <Ed> g[N], gr[N]; int get1n(int u, int v) { return dist1[u] + distn_rev[v]; } int getn1(int u, int v) { return distn[u] + dist1_rev[v]; } int get1n(int i) { return get1n(e[i].u, e[i].v) + e[i].c; } int getn1(int i) { return getn1(e[i].u, e[i].v) + e[i].c; } void dj(int S, int *dist, vector <Ed> g[N], int par[N], int par_ed[N], int sec[N], int best[N]) { for (int i = 0; i < N; ++i) { dist[i] = INF; best[i] = -1; sec[i] = INF; } set <ii> ms; dist[S] = 0; ms.insert(mp(0, S)); while (ms.size()) { int u = ms.begin()->s; ms.erase(ms.begin()); for (auto e : g[u]) { if (dist[u] + e.c < dist[e.v]) { ms.erase(mp(dist[e.v], e.v)); sec[e.v] = dist[e.v]; dist[e.v] = dist[u] + e.c; par[e.v] = u; par_ed[e.v] = e.i; best[e.v] = e.i; ms.insert(mp(dist[e.v], e.v)); } else { sec[e.v] = min(sec[e.v], dist[u] + e.c); } } } } int from1(int u, int ban) { if (ban != best1[u]) return dist1[u]; else return sec1[u]; } int ton(int u, int ban) { if (ban != bestn_rev[u]) return distn_rev[u]; else return secn_rev[u]; } int fromn(int u, int ban) { if (ban != bestn[u]) return distn[u]; else return secn[u]; } int to1(int u, int ban) { if (ban != best1_rev[u]) return dist1_rev[u]; else return sec1_rev[u]; } int dist1n_del[N], distn1_del[N]; vector <int> tree[N], add[N], del[N]; bool used[N]; const int LG = 20; int to[N][LG], tin[N], tout[N], timer = 0; void dfs1(int u, int p) { to[u][0] = p; for (int i = 1; i < LG; ++i) to[u][i] = to[to[u][i - 1]][i - 1]; tin[u] = timer++; for (int v : tree[u]) dfs1(v, u); tout[u] = timer++; } bool anc(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; } bool vert(int u, int v) { return anc(u, v) || anc(v, u); } int lca(int u, int v) { if (anc(u, v)) return u; for (int i = LG - 1; i >= 0; --i) if (!anc(to[u][i], v)) u = to[u][i]; return to[u][0]; } bool inp1[N], inpn[N]; int getup(int u, int v) { if (anc(u, v)) return u; else return v; } int mmin(int u, int v) { if (anc(u, v)) return v; else return u; } void upd(int &a, int b) { if (a == -1) a = b; else a = mmin(a, b); } signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n >> m; for (int i = 0; i < m; ++i) { cin >> e[i].u >> e[i].v >> e[i].c >> e[i].d; g[e[i].u].app({e[i].v, e[i].c, i}); gr[e[i].v].app({e[i].u, e[i].c, i}); } dj(1, dist1, g, par1, par_ed1, sec1, best1); dj(n, distn, g, parn, par_edn, secn, bestn); dj(1, dist1_rev, gr, tmp, tmp, sec1_rev, best1_rev); dj(n, distn_rev, gr, tmp, tmp, secn_rev, bestn_rev); for (int i = 2; i <= n; ++i) if (par1[i]) { tree[par1[i]].app(i); used[par_ed1[i]] = 1; } dfs1(1, 1); /* for (int i = 1; i <= n; ++i) cout << par1[i] << ' '; cout << '\n'; */ for (int i = 0; i < m; ++i) { if (!used[i]) { int l = lca(e[i].u, e[i].v); l = lca(l, n); int x = get1n(i); add[lca(e[i].u, n)].app(x); del[l].app(x); add[lca(e[i].v, n)].app(x); del[l].app(x); } } if (!par1[n]) { for (int i = 0; i < N; ++i) dist1n_del[i] = INF; } else { for (int i = 0; i < N; ++i) dist1n_del[i] = dist1[n]; int u = n; multiset <int> ms = {INF}; while (u != 1) { //cout << "up " << u << '\n'; for (int e : add[u]) { ms.insert(e); //cout << "insert " << e << '\n'; } for (int e : del[u]) { ms.erase(ms.find(e)); //cout << "erase " << e << '\n'; } dist1n_del[par_ed1[u]] = *ms.begin(); inp1[par_ed1[u]] = 1; u = to[u][0]; } } for (int i = 0; i < N; ++i) { tree[i].clear(); add[i].clear(); del[i].clear(); } memset(used, 0, sizeof used); for (int i = 1; i < n; ++i) if (parn[i]) { tree[parn[i]].app(i); used[par_edn[i]] = 1; } dfs1(n, n); for (int i = 0; i < m; ++i) { if (!used[i]) { int l = lca(e[i].u, e[i].v); l = lca(l, 1); int x = getn1(i); add[lca(e[i].u, 1)].app(x); del[l].app(x); add[lca(e[i].v, 1)].app(x); del[l].app(x); } } if (!parn[1]) { for (int i = 0; i < N; ++i) distn1_del[i] = INF; } else { for (int i = 0; i < N; ++i) distn1_del[i] = distn[1]; int u = 1; multiset <int> ms = {INF}; while (u != n) { for (int e : add[u]) ms.insert(e); for (int e : del[u]) ms.erase(ms.find(e)); distn1_del[par_edn[u]] = *ms.begin(); inpn[par_edn[u]] = 1; u = to[u][0]; } } #ifdef HOME for (int i = 0; i < m; ++i) cout << dist1n_del[i] << ' '; cout << '\n'; for (int i = 0; i < m; ++i) cout << distn1_del[i] << ' '; cout << '\n'; #endif int ans = dist1[n] + distn[1]; for (int i = 0; i < m; ++i) { int d1n = INF, dn1 = INF; if (!inp1[i]) d1n = from1(e[i].v, i) + ton(e[i].u, i) + e[i].c; if (!inpn[i]) dn1 = fromn(e[i].v, i) + to1(e[i].u, i) + e[i].c; d1n = min(d1n, dist1n_del[i]); dn1 = min(dn1, distn1_del[i]); ans = min(ans, d1n + dn1 + e[i].d); //cout << i << ' ' << d1n << ' ' << dn1 << ' ' << e[i].d << '\n'; } if (ans > 1e12) cout << "-1\n"; else cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...