Submission #58690

#TimeUsernameProblemLanguageResultExecution timeMemory
58690ksun48Wild Boar (JOI18_wild_boar)C++14
100 / 100
16072 ms361208 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MAXD = (1LL << 60LL); int n, m, t, l; vector<int> a, b; vector<LL> c; typedef pair<LL, pair<int,int> > Path; typedef vector<Path> OptPaths; int unused = 3000; Path new_unused(){ Path x = {MAXD, {unused,unused}}; //unused ++; return x; } Path alt_path(pair<int,int> avoid, OptPaths& paths){ Path f = new_unused(); for(Path x : paths){ if(x.second.first != avoid.first && x.second.second != avoid.second){ if(x.first < f.first){ f = x; } } } return f; } Path alt_path2(pair<int,int> avoid, OptPaths& paths){ Path f = new_unused(); for(Path x : paths){ if(x.second.first != avoid.first || x.second.second != avoid.second){ if(x.first < f.first){ f = x; } } } return f; } int np = 0; OptPaths process(OptPaths cand){ np++; OptPaths edges; if(cand.size() == 0) return edges; edges.push_back(alt_path({-1, -1}, cand)); pair<int,int> x = edges[0].second; if(edges[0].first >= MAXD) return edges; edges.push_back(alt_path2(x, cand)); pair<int,int> y = edges[1].second; if(edges[1].first >= MAXD) return edges; if(x.first != y.first && x.second != y.second){ edges.push_back(alt_path({x.first, y.second}, cand)); edges.push_back(alt_path({y.first, x.second}, cand)); } else if(x.first == y.first){ Path q = alt_path({x.first, -1}, cand); edges.push_back(q); edges.push_back(alt_path({x.first, q.second.second}, cand)); } else if(x.second == y.second){ Path q = alt_path({-1, x.second}, cand); edges.push_back(q); edges.push_back(alt_path({q.second.first, x.second}, cand)); } sort(edges.begin(), edges.end()); while(edges.size() > 0 && edges[edges.size() - 1].first >= MAXD) edges.pop_back(); return edges; } OptPaths join(OptPaths a, OptPaths b){ OptPaths cand; for(auto x : a){ for(auto y : b){ if(x.second.second != y.second.first){ cand.push_back({min(x.first + y.first, MAXD), {x.second.first, y.second.second}}); } } } return cand; } vector<vector<OptPaths> > cachedpaths; void compute_paths2(int s){ // start bellman-ford at s vector<OptPaths> sssp(n); for(int id = 0; id < m; id++){ if(a[id] != s && b[id] != s) continue; if(b[id] == s) swap(a[id], b[id]); // all paths starting with edge id int st = b[id]; vector<vector<int> > adj(n); for(int i = 0; i < m; i++){ if(a[i] != s && b[i] != s){ adj[a[i]].push_back(i); adj[b[i]].push_back(i); } } int vis[n][2]; pair<LL,int> dist[n][2]; int changed[n]; for(int i = 0; i < n; i++){ changed[i] = 0; vis[i][0] = vis[i][1] = 0; dist[i][0] = {MAXD, -2}; dist[i][1] = {MAXD, -1}; } dist[st][0] = {c[id], id}; dist[st][1] = {MAXD, -1}; changed[st] = 1; set<pair<LL,int> > stuff; for(int i = 0; i < n; i++){ if(i != s){ stuff.insert({dist[i][0].first, (i << 1)}); } } while(!stuff.empty()){ pair<LL,int> x = *stuff.begin(); stuff.erase(stuff.begin()); int v = x.second >> 1; int idx = x.second & 1; vis[v][idx] = 1; if(!changed[v]) continue; changed[v] = 0; for(auto i : adj[v]){ if(b[i] == v){ swap(a[i], b[i]); } int w = b[i]; if(vis[w][0] && vis[w][1]) continue; LL d = 0; if(dist[v][0].second != i){ d = min(MAXD, dist[v][0].first + c[i]); } else { d = min(MAXD, dist[v][1].first + c[i]); } for(int j = 0; j < 2; j++){ if(!vis[w][j]){ stuff.erase({dist[w][j].first, (w << 1) ^ j}); break; } } if(dist[w][0].second == i){ if(d < dist[w][0].first){ changed[w] = 1; dist[w][0] = {d, i}; } } else if(dist[w][1].second == i){ if(d < dist[w][1].first){ changed[w] = 1; dist[w][1] = {d, i}; } } else if(d < dist[w][1].first){ changed[w] = 1; dist[w][1] = {d, i}; } if(dist[w][0] > dist[w][1]) swap(dist[w][0], dist[w][1]); for(int j = 0; j < 2; j++){ if(!vis[w][j]){ stuff.insert({dist[w][j].first, (w << 1) ^ j}); break; } } } } for(int i = 0; i < n; i++){ if(i == s) continue; sssp[i].push_back({dist[i][0].first,{id,dist[i][0].second}}); sssp[i].push_back({dist[i][1].first,{id,dist[i][1].second}}); } } for(int i = 0; i < n; i++){ if(i == s) continue; sssp[i] = process(sssp[i]); } cachedpaths[s] = sssp; } vector<int> plan; struct node { node *l, *r; int lidx, ridx; OptPaths paths; }; node * build(int l, int r){ node * f = new node(); f->lidx = l; f->ridx = r; if(l == r){ f->l = f->r = NULL; f->paths = cachedpaths[plan[l]][plan[l+1]]; } else { int m = (l + r) / 2; f->l = build(l, m); f->r = build(m + 1, r); f->paths = process(join(f->l->paths, f->r->paths)); } return f; } void upd(node * v, int x){ if(v == NULL) return; if(v->ridx < x-1 || v->lidx > x) return; if(v->lidx == v->ridx){ if(v->lidx == x-1){ v->paths = cachedpaths[plan[x-1]][plan[x]]; } else if(v->lidx == x){ v->paths = cachedpaths[plan[x]][plan[x+1]]; } } else { upd(v->l, x); upd(v->r, x); v->paths = process(join(v->l->paths, v->r->paths)); } } int main(){ cin.sync_with_stdio(0); cin.tie(0); cin >> n >> m >> t >> l; cachedpaths.resize(n); a.resize(m); b.resize(m); c.resize(m); for(int i = 0; i < m; i++){ cin >> a[i] >> b[i] >> c[i]; a[i]--; b[i]--; } plan.resize(l); vector<int> need(n, 0); for(int i = 0; i < l; i++){ cin >> plan[i]; plan[i]--; need[plan[i]] = 1; } vector<pair<int,int> > updates(t); for(int i = 0; i < t; i++){ cin >> updates[i].first >> updates[i].second; updates[i].first--; updates[i].second--; need[updates[i].second] = 1; } for(int i = 0; i < n; i++){ compute_paths2(i); //cout << "done " << i << endl; } node * tree = build(0, l - 2); for(int tt = 0; tt < t; tt++){ int x = updates[tt].first; plan[x] = updates[tt].second; upd(tree, x); OptPaths& route = tree->paths; cout << (route.size() > 0 && route[0].first < MAXD ? route[0].first : -1) << '\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...