Submission #564681

#TimeUsernameProblemLanguageResultExecution timeMemory
564681maomao90Wild Boar (JOI18_wild_boar)C++17
62 / 100
18096 ms884432 KiB
// 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 second typedef 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_back typedef 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]; int w[MAXN * 3]; int x[MAXL]; ll rd[MAXN][MAXN][BAG]; int fi[MAXN][MAXN][BAG], se[MAXN][MAXN][BAG]; ll dp[MAXL][BAG]; int par[MAXN][2]; ll dist[MAXN * 3][MAXN * 3][2]; 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; } REP (i, 0, n + 1) { par[i][0] = par[i][1] = -1; if (s <= n) { fi[s][i][0] = se[s][i][0] = -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]) { int cpar = par[u][tp]; if (u <= n && v > n && (v ^ 1) == cpar) { continue; } if (u > n) { cpar = adj[u ^ 1][0]; } ll nd = d + w[v]; if (mnto(dist[s][v][0], nd)) { pq.push(tll{nd, v, 0}); if (v <= n) { if (s <= n) { fi[s][v][0] = fi[s][cpar][0] == -1 ? u : fi[s][cpar][0]; se[s][v][0] = u; } par[v][0] = u; } } else if (mnto(dist[s][v][1], nd) && v <= n && par[v][0] != u) { 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); e++; w[e] = c; adj[b].pb(e); adj[e].pb(a); 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]; for (int u : adj[i]) { for (int v : adj[j]) { v ^= 1; REP (z, 1, 3) { if ((z == 1 && u == fi[i][j][0]) || (z == 2 && v == se[i][j][0])) { continue; } if (mnto(rd[i][j][z], dist[u][v][0])) { fi[i][j][z] = u; se[i][j][z] = v; } } } } if (rd[i][j][1] != LINF) { for (int u : adj[i]) { for (int v : adj[j]) { v ^= 1; if (u == fi[i][j][0] || v == se[i][j][1]) continue; if (mnto(rd[i][j][3], dist[u][v][0])) { fi[i][j][3] = u; se[i][j][3] = v; } } } } if (rd[i][j][2] != LINF) { for (int u : adj[i]) { for (int v : adj[j]) { v ^= 1; if (u == fi[i][j][2] || v == se[i][j][0]) continue; if (mnto(rd[i][j][4], dist[u][v][0])) { fi[i][j][4] = u; se[i][j][4] = v; } } } } REP (z, 0, BAG) { cerr << i << ' ' << j << ' ' << z << ": " << rd[i][j][z] << ' ' << fi[i][j][z] << ' ' << se[i][j][z] << '\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 && (se[p][u][k] ^ 1) == fi[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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...