Submission #58506

#TimeUsernameProblemLanguageResultExecution timeMemory
58506ksun48Wild Boar (JOI18_wild_boar)C++14
12 / 100
18023 ms1148 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){ for(Path x : paths){ if(x.second.first == avoid.first) continue; if(x.second.second == avoid.second) continue; return x; } return new_unused(); } OptPaths process(OptPaths cand){ sort(cand.begin(), cand.end()); OptPaths edges; pair<int,int> x = cand[0].second; edges.push_back(cand[0]); pair<int,int> y; for(int i = 0; i < cand.size(); i++){ if(cand[i].second == x) continue; y = cand[i].second; edges.push_back(cand[i]); break; } if(edges.size() == 1){ Path q = new_unused(); y = q.second; edges.push_back(q); } 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()); 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; } OptPaths edge(int id, LL cost){ OptPaths x; x.push_back({cost, {id, id}}); return x; } OptPaths best_paths(int s, int t){ assert(s != t); // start bellman-ford at s OptPaths sssp[n]; for(int i = 0; i < n; i++){ unused++; sssp[i] = edge(unused-1, MAXD); } for(int i = 0; i < m; i++){ if(a[i] == s){ sssp[b[i]] = edge(i, c[i]); } else if(b[i] == s){ sssp[a[i]] = edge(i, c[i]); } } for(int j = 0; j < 2 * n + 2; j++){ for(int i = 0; i < m; i++){ if(a[i] == s || b[i] == s) continue; OptPaths e = edge(i, c[i]); OptPaths x = join(sssp[a[i]], e); x.insert(x.end(), sssp[b[i]].begin(), sssp[b[i]].end()); sssp[b[i]] = process(x); } for(int i = 0; i < m; i++){ if(a[i] == s || b[i] == s) continue; OptPaths e = edge(i, c[i]); OptPaths x = join(sssp[b[i]], e); x.insert(x.end(), sssp[a[i]].begin(), sssp[a[i]].end()); sssp[a[i]] = process(x); } } return sssp[t]; } int main(){ cin.sync_with_stdio(0); cin.tie(0); cin >> n >> m >> t >> l; 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]--; } vector<int> plan(l); for(int i = 0; i < l; i++){ cin >> plan[i]; plan[i]--; } 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--; } /*for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cout << "paths from " << i << " to " << j << '\n'; if(i != j){ OptPaths x = best_paths(i, j); for(auto v : x){ cout << v.second.first << " " << v.second.second << " " << v.first << '\n'; } } } }*/ for(int tt = 0; tt < t; tt++){ plan[updates[tt].first] = updates[tt].second; OptPaths route = best_paths(plan[0], plan[1]); for(int j = 2; j < l; j++){ route = process(join(route, best_paths(plan[j-1], plan[j]) ) ); } cout << (route[0].first < MAXD ? route[0].first : -1) << '\n'; } }

Compilation message (stderr)

wild_boar.cpp: In function 'OptPaths process(OptPaths)':
wild_boar.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cand.size(); i++){
                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...