| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1028932 | AdamGS | Escape Route (JOI21_escape_route) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=107;
pair<ll,ll>T[LIM][LIM];
vector<vector<ll>>X[LIM];
vector<ll>P[LIM], K[LIM];
ll li[LIM], n, S, q;
void calc1() {
rep(i, n) {
rep(j, n) P[i].pb(INF);
vector<ll>odw(n);
P[i][i]=0;
while(true) {
pair<ll,ll>mi={INF, INF};
rep(j, n) if(!odw[j]) mi=min(mi, {P[i][j], j});
if(mi.st==INF) break;
ll p=mi.nd;
odw[p]=1;
rep(j, n) if(!odw[j] && T[p][j].nd!=-1) {
ll a=mi.st/S, b=mi.st%S;
if(b<=T[p][j].nd-T[p][j].st) P[i][j]=min(P[i][j], mi.st+T[p][j].st);
else P[i][j]=min(P[i][j], (a+1)*S+T[p][j].st);
}
}
}
}
vector<ll>calc2(ll a, ll b) {
vector<ll>odl(n, INF), odw(n);
odl[a]=0;
while(true) {
pair<ll,ll>mi={INF, INF};
rep(i, n) if(!odw[i]) mi=min(mi, {odl[i], i});
if(mi.st==INF) break;
ll p=mi.nd;
odw[p]=1;
rep(i, n) if(!odw[i] && T[p][i].nd!=-1) {
if(mi.st+b<=T[p][i].nd-T[p][i].st) odl[i]=min(odl[i], mi.st+T[p][i].st);
}
}
return odl;
}
void solve(ll x, ll l, ll r) {
if(l==r) return;
ll mid=(l+r+1)/2;
vector<ll>A=calc2(x, l), B=calc2(x, mid), C=calc2(x, r);
if(A!=B) {
if(l+1==mid) {
X[x].pb(B);
K[x].pb(mid);
} else solve(x, l, mid);
}
if(B!=C) solve(x, mid, r);
}
vector<ll>calculate_necessary_time(int _n, int _m, ll _S, int _q, vector<int>_A, vector<int>_B,
vector<ll>_L, vector<ll>_C, vector<int>_U, vector<int>_V, vector<ll>_T) {
n=_n; S=_S; q=_q;
rep(i, n) rep(j, n) T[i][j]={0, -1};
rep(i, _m) T[_A[i]][_B[i]]=T[_B[i]][_A[i]]={_L[i], _C[i]};
calc1();
rep(i, n) {
X[i].pb(calc2(i, 0));
K[i].pb(0);
solve(i, 0, S-1);
rep(j, X[i].size()) {
rep(l, n) if(X[i][j][l]==INF) X[i][j][l]=2*INF;
rep(l, n) if(X[i][j][l]<INF) {
rep(d, n) X[i][j][d]=min(X[i][j][d], INF+S+P[l][d]);
}
}
}
vector<ll>ans(q, INF);
vector<pair<ll,ll>>pyt(q);
rep(i, q) pyt[i]={_T[i], i};
sort(all(pyt));
for(auto xd : pyt) {
int i=xd.nd;
ll a=_U[i], b=_V[i], c=_T[i];
while(li[a]+1<K[a].size() && K[a][li[a]+1]<=c) {
++li[a];
}
ll po=li[a];
if(X[a][po][b]<INF) {
ans[i]=X[a][po][b];
continue;
}
ans[i]=X[a][po][b]-INF-c;
}
return ans;
}
int main() {
ll _n, _m, _S, _q;
cin >> _n >> _m >> _S >> _q;
vector<int>_A(_m), _B(_m), _U(_q), _V(_q);
vector<ll>_L(_m), _C(_m), _T(_q);
rep(i, _m) cin >> _A[i] >> _B[i] >> _L[i] >> _C[i];
rep(i, _q) cin >> _U[i] >> _V[i] >> _T[i];
vector<ll>_ans=calculate_necessary_time(_n, _m, _S, _q, _A, _B, _L, _C, _U, _V, _T);
for(auto i : _ans) cout << i << '\n';
}