| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 564294 | maomao90 | Wild Boar (JOI18_wild_boar) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Hallelujah, praise the one who set me free// Hallelujah, death has lost its grip on me// You have broken every chain, There's salvation in your name// Jesus Christ, my living hope#include <bits/stdc++.h> using namespace std; template <class T>inline bool mnto(T& a, T b) {return a >= b ? a = b, 1 : 0;}template <class T>inline bool mxto(T& a, T b) {return a <= b ? a = b, 1: 0;}#define REP(i, s, e) for (int i = s; i < e; i++)#define RREP(i, s, e) for (int i = s; i >= e; i--)typedef long long ll;typedef long double ld;#define FI first#define SE secondtypedef pair<int, int> ii;typedef pair<ll, ll> pll;typedef tuple<int, int, int> iii;typedef tuple<ll, ll, ll> tll;#define ALL(_a) _a.begin(), _a.end()#define pb push_backtypedef vector<int> vi;typedef vector<ll> vll;typedef vector<ii> vii;typedef vector<iii> viii; #ifndef DEBUG#define cerr if (0) cerr#endif const int INF = 1000000005;const ll LINF = 1000000000000000005ll;const int MAXN = 2005;const int MAXL = 100005;const int BAG = 5; int n, m, t, l, e;vi adj[MAXN * 3], radj[MAXN];int w[MAXN * 3];int x[MAXL];ll rd[MAXN][MAXN][BAG];int rfi[MAXN][MAXN][BAG], rse[MAXN][MAXN][BAG];ll dp[MAXL][BAG]; int par[MAXN * 3][2];ll dist[MAXN * 3][MAXN * 3][2];int fi[MAXN * 3][MAXN * 3], se[MAXN * 3][MAXN * 3];priority_queue<tll, vector<tll>, greater<tll>> pq;void dijkstra(int s) { REP (i, 0, e) { dist[s][i][0] = dist[s][i][1] = LINF; fi[s][i] = se[s][i] = -1; par[i][0] = par[i][1] = -1; } dist[s][s][0] = w[s]; pq.push(tll{w[s], s, 0}); while (!pq.empty()) { auto [d, u, tp] = pq.top(); pq.pop(); if (d != dist[s][u][tp]) continue; for (int v : adj[u]) { if (v > n && (v ^ 1) == par[u][tp]) { continue; } ll nd = d + w[v]; if (mnto(dist[s][v][0], nd)) { if (par[v][0] != -1 && par[v][0] != u) { dist[s][v][1] = dist[s][v][0]; par[v][1] = par[v][0]; pq.push(tll{dist[s][v][1], v, 1}); } pq.push(tll{nd, v, 0}); fi[s][v] = fi[s][u] == -1 ? v : fi[s][u]; se[s][v] = u; par[v][0] = u; } else if (mnto(dist[s][v][1], nd)) { pq.push(tll{nd, v, 1}); par[v][1] = u; } } }} int main() {#ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0);#endif cin >> n >> m >> t >> l; e = n + 1; if (e & 1) { e++; } REP (i, 0, m) { int a, b, c; cin >> a >> b >> c; w[e] = c; adj[a].pb(e); adj[e].pb(b); radj[a].pb(e++); w[e] = c; adj[b].pb(e); adj[e].pb(a); radj[b].pb(e++); } REP (i, 1, e) { dijkstra(i); } REP (i, 1, n + 1) { REP (j, 1, n + 1) { if (i == j) continue; REP (z, 0, BAG) { rd[i][j][z] = LINF; } rd[i][j][0] = dist[i][j][0]; rfi[i][j][0] = fi[i][j]; rse[i][j][0] = se[i][j]; for (int u : radj[i]) { for (int v : radj[j]) { v ^= 1; REP (z, 1, 3) { if ((z == 1 && u == fi[i][j]) || (z == 2 && v == se[i][j])) { continue; } cerr << u << ' ' << v << ' ' << z << '\n'; if (mnto(rd[i][j][z], dist[u][v][0])) { rfi[i][j][z] = u; rse[i][j][z] = v; } } } } if (rd[i][j][1] != LINF) { for (int u : radj[i]) { for (int v : radj[j]) { v ^= 1; if (u == fi[i][j] || v == rse[i][j][1]) continue; if (mnto(rd[i][j][3], dist[u][v][0])) { rfi[i][j][3] = u; rse[i][j][3] = v; } } } } if (rd[i][j][2] != LINF) { for (int u : radj[i]) { for (int v : radj[j]) { v ^= 1; if (u == rfi[i][j][2] || v == se[i][j]) continue; if (mnto(rd[i][j][4], dist[u][v][0])) { rfi[i][j][4] = u; rse[i][j][4] = v; } } } } REP (z, 0, BAG) { cerr << i << ' ' << j << ' ' << z << ": " << rd[i][j][z] << ' ' << rfi[i][j][z] << ' ' << rse[i][j][z] << '\n'; } cerr << ' ' << fi[i][j] << ' ' << se[i][j] << '\n'; } } x[0] = -1; REP (i, 1, l + 1) { cin >> x[i]; } while (t--) { int p, q; cin >> p >> q; x[p] = q; REP (j, 0, BAG) { dp[1][j] = 0; } REP (i, 2, l + 1) { int p = x[i - 2], u = x[i - 1], v = x[i]; REP (j, 0, BAG) { dp[i][j] = LINF; REP (k, 0, BAG) { if (p != -1 && (rse[p][u][k] ^ 1) == rfi[u][v][j]) continue; mnto(dp[i][j], dp[i - 1][k] + rd[u][v][j]); } cerr << i << ' ' << j << ": " << dp[i][j] << '\n'; } } ll ans = LINF; REP (j, 0, BAG) { mnto(ans, dp[l][j]); } if (ans >= LINF) { ans = -1; } cout << ans << '\n'; } return 0;}