제출 #415764

#제출 시각아이디문제언어결과실행 시간메모리
415764koioi.org-koosagaEscape Route (JOI21_escape_route)C++17
35 / 100
9020 ms196984 KiB
#include "escape_route.h" #include <bits/stdc++.h> #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() using namespace std; using lint = long long; using pi = pair<lint, lint>; struct edg{ int pos; lint L, C; }; struct node{ int i, j; lint max_time; bool operator<(const node &n)const{ return max_time < n.max_time; } }; lint daybreak[96][96]; lint dayfinish[96][96]; lint adj[96][96], dp[96][96]; vector<edg> gph[96]; vector<pi> prec[96][96]; lint S; void do_prec(int s, int n){ priority_queue<pi, vector<pi>, greater<pi>> pq[96]; // (dist, weight) pq[s].emplace(0, -S); for(int i = 0; i < n; i++) prec[s][i].emplace_back(-1, 1); while(true){ pi ans(1e18, 1e18); for(int i = 0; i < n; i++){ while(sz(pq[i]) && (pq[i].top().first <= prec[s][i].back().first || -pq[i].top().second <= -prec[s][i].back().second)) pq[i].pop(); if(sz(pq[i])){ ans = min(ans, pi(pq[i].top().first, i)); } } if(ans.second > n) break; int pos = ans.second; prec[s][pos].push_back(pq[pos].top()); lint cur_dist = pq[pos].top().first; lint cur_weight = -pq[pos].top().second; pq[pos].pop(); for(auto &j : gph[pos]){ lint new_dist = cur_dist + j.L; lint new_weight = min(cur_weight, j.C - new_dist); if(new_weight < 0) continue; pq[j.pos].emplace(new_dist, -new_weight); } } for(int i = 0; i < n; i++){ for(auto &[x, y] : prec[s][i]){ // printf("prev %d %d %lld %lld\n", s, i, x, y); tie(x, y) = pi(-y, x); } for(int j = 0; j < sz(prec[s][i])-1; j++){ prec[s][i][j].second = prec[s][i][j + 1].second; } prec[s][i].back().second = 1e18; for(auto &[x, y] : prec[s][i]){ x++; // printf("%d %d %lld %lld\n", s, i, x, y); } } } // wtf just use namespace std and pairs std::vector<long long> calculate_necessary_time( int N, int M, long long Sfuck, int Q, std::vector<int> A, std::vector<int> B, std::vector<long long> L, std::vector<long long> C, std::vector<int> U, std::vector<int> V, std::vector<long long> T) { S = Sfuck; for(int i = 0; i < M; i++){ gph[A[i]].push_back({B[i], L[i], C[i]}); gph[B[i]].push_back({A[i], L[i], C[i]}); } { priority_queue<node> pq; memset(daybreak, 0x3f, sizeof(daybreak)); auto enq = [&](int s, int e, lint x){ if(daybreak[s][e] > x){ daybreak[s][e] = x; pq.push({s, e, -x}); } }; for(int i = 0; i < N; i++){ enq(i, i, 0); } while(sz(pq)){ auto x = pq.top(); pq.pop(); x.max_time = -x.max_time; if(daybreak[x.i][x.j] != x.max_time) continue; for(auto &e : gph[x.j]){ if(x.max_time + e.L <= e.C){ enq(x.i, e.pos, x.max_time + e.L); } } } } { priority_queue<node> pq; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ dayfinish[i][j] = -1e18; } } auto enq = [&](int s, int e, lint x){ if(dayfinish[s][e] < x){ dayfinish[s][e] = x; pq.push({s, e, x}); } }; for(int i = 0; i < N; i++){ enq(i, i, S); } while(sz(pq)){ auto x = pq.top(); pq.pop(); if(dayfinish[x.i][x.j] != x.max_time) continue; for(auto &e : gph[x.i]){ lint val = min(x.max_time, e.C) - e.L; if(val >= 0) enq(e.pos, x.j, val); } } } { memset(adj, 0x3f, sizeof(adj)); for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ if(dayfinish[i][j] >= 0) adj[i][j] = 1; if(i == j) adj[i][j] = 0; } } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ for(int k = 0; k < N; k++){ adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]); } } } for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ assert(adj[i][j] <= N); dp[i][j] = 1e18; for(int k = 0; k < N; k++){ dp[i][j] = min(adj[i][k] * S + daybreak[k][j], dp[i][j]); } } } } for(int i = 0; i < N; i++){ do_prec(i, N); } vector<lint> ans(Q); for(int i = 0; i < Q; i++){ if(dayfinish[U[i]][V[i]] >= T[i]){ auto it = upper_bound(all(prec[U[i]][V[i]]), pi(T[i] + 1, -1)); ans[i] = prev(it)->second; continue; } lint ret = 1e18; for(int j = 0; j < N; j++){ if(dayfinish[U[i]][j] >= T[i]){ ret = min(ret, S - T[i] + dp[j][V[i]]); } } ans[i] = ret; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...