제출 #60968

#제출 시각아이디문제언어결과실행 시간메모리
60968BenqWild Boar (JOI18_wild_boar)C++11
62 / 100
18077 ms494612 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 2001; typedef array<ll,3> T; // distance, begin, end T ori = {INF,INF,INF}; template<class T> void MN (T& a, T b) { a = min(a,b); } struct dat { pi path; vector<T> besPath; dat() {} dat(pi _path, vector<T> _besPath) { path = _path; T bes[4]; F0R(i,4) bes[i] = ori; for (auto a: _besPath) MN(bes[0],a); for (auto a: _besPath) if (a[1] != bes[0][1] || a[2] != bes[0][2]) MN(bes[1],a); /*if (bes[0][1] == bes[1][1] && bes[0][2] == bes[1][2]) { cout << "AH " << path.f << " " << path.s << " " << bes[0][1] << " " << bes[0][2]; exit(0); }*/ if (bes[0][1] == bes[1][1]) { // same x for (auto a: _besPath) if (a[1] != bes[0][1]) MN(bes[2],a); for (auto a: _besPath) if (a[1] != bes[0][1] && a[2] != bes[2][2]) MN(bes[3],a); } else if (bes[0][2] == bes[1][2]) { // same y for (auto a: _besPath) if (a[2] != bes[0][2]) MN(bes[2],a); for (auto a: _besPath) if (a[1] != bes[2][1] && a[2] != bes[0][2]) MN(bes[3],a); } else { for (auto a: _besPath) if (a[1] != bes[0][1] && a[2] != bes[1][2]) MN(bes[2],a); for (auto a: _besPath) if (a[1] != bes[1][1] && a[2] != bes[0][2]) MN(bes[3],a); } F0R(i,4) if (bes[i][0] != INF) besPath.pb(bes[i]); } }; dat comb(const dat& l, const dat& r) { assert(l.path.s == r.path.f); vector<T> cand; for (auto a: l.besPath) for (auto b: r.besPath) if (a[2] != b[1]) cand.pb({a[0]+b[0],a[1],b[2]}); return dat({l.path.f,r.path.s},cand); } template<int SZ> struct Dijkstra { pl dist[SZ][2]; vpi adj[SZ]; void addEdge(int A, int B, int C) { adj[A].pb({B,C}), adj[B].pb({A,C}); } void gen(T tmp) { F0R(i,SZ) F0R(j,2) dist[i][j] = {INF,INF}; priority_queue<T,vector<T>,greater<T>> q; dist[tmp[2]][0] = {tmp[0],tmp[1]}; q.push(tmp); while (sz(q)) { auto x = q.top(); q.pop(); bool ok = 0; F0R(j,2) if (dist[x[2]][j] == mp(x[0],x[1])) ok = 1; if (!ok) continue; for (pi y: adj[x[2]]) { if (y.f == x[1]) continue; if (x[0]+y.s < dist[y.f][0].f) { if (dist[y.f][0].s != x[2]) dist[y.f][1] = dist[y.f][0]; dist[y.f][0] = {x[0]+y.s,x[2]}; q.push({x[0]+y.s,x[2],y.f}); } else { if (x[2] == dist[y.f][0].s) continue; if (x[0]+y.s < dist[y.f][1].f) { dist[y.f][1] = {x[0]+y.s,x[2]}; q.push({x[0]+y.s,x[2],y.f}); } } } } } }; Dijkstra<MX> D; int N,M,t,L; dat d[MX][MX]; void init() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M >> t >> L; F0R(i,M) { int A,B,C; cin >> A >> B >> C; D.addEdge(A,B,C); } } ll get(vl X) { dat z = d[X[0]][X[1]]; FOR(i,2,sz(X)) z = comb(z,d[X[i-1]][X[i]]); ll ans = INF; for (auto a: z.besPath) ans = min(ans,a[0]); if (ans == INF) ans = -1; return ans; } int main() { init(); vector<T> path[MX]; FOR(i,1,N+1) { for (pi j: D.adj[i]) { D.gen({j.s,i,j.f}); FOR(k,1,N+1) if (k != i) F0R(z,2) if (D.dist[k][z].f != INF) path[k].pb({D.dist[k][z].f,j.f,D.dist[k][z].s}); } FOR(k,1,N+1) if (k != i) { /*if (k == 1) { for (auto a: path[k]) cout << "HI " << a[0] << " " << a[1] << " " << a[2] << "\n"; }*/ d[i][k] = dat({i,k},path[k]); /*if (k == 1) { for (auto a: d[i][k].besPath) cout << "hi " << a[0] << " " << a[1] << " " << a[2] << "\n"; exit(0); }*/ path[k].clear(); } } vl X(L); F0R(i,L) cin >> X[i]; F0R(i,t) { int p,q; cin >> p >> q; X[p-1] = q; /*FOR(j,2,sz(X)+1) { vl XX = vl(X.begin(),X.begin()+j); cout << get(XX) << "\n"; }*/ cout << get(X) << "\n"; } } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...