#include "escape_route.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <vector>
#include <iostream>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=30;
const int mxQ=3000500;
const int mxK=60;
const ll INF=1e18;
struct Time{
ll t, a, b;
Time() : t(), a(), b() {}
Time(ll t, ll a, ll b) : t(t), a(a), b(b) {}
};
pll adj[mxN][mxN];
ll N, M, S, Q;
ll qry[mxQ][3];
Time dist[mxN][mxN][mxN*mxN/2];
Time tmpt[mxN*mxN];
Time ttmpt[mxN*mxN];
int sztmp, szttmp;
int siz[mxN][mxN];
void input(){
cin >> N >> M >> S >> Q;
for(int i=1;i<=M;i++){
int s, e;
ll x, l;
cin >> s >> e >> x >> l;
s++; e++;
adj[s][e]=pll(x, l);
adj[e][s]=pll(x, l);
}
for(int i=0;i<Q;i++){
cin >> qry[i][0] >> qry[i][1] >> qry[i][2];
qry[i][0]++, qry[i][1]++;
}
}
ll Sdist(ll a, ll b){return b>a ? b-a : b-a+S;}
void mrg(int s, int e, int mid){
if(siz[s][mid]==0 || siz[mid][e]==0){
sztmp=0;
return;
}
int idxs=0, idxe=0, idx=0;
for(int i=0;i<siz[s][mid];i++){
auto [st, sa, sb]=dist[s][mid][i];
pll start_t=pll(st, (i==siz[s][mid]-1 ? S-1 : dist[s][mid][i+1].t-1));
pll mid_t=pll(sa*start_t.fi+sb, sa*start_t.se+sb), mid_r=pll(mid_t.fi%S, mid_t.se%S);
// idxe 시작점 맞추기
while(true){
ll l=dist[mid][e][idxe].t, r=(idxe==siz[mid][e]-1 ? S : dist[mid][e][idxe+1].t);
if(l<=mid_r.fi && mid_r.fi<r) break;
idxe=(idxe==siz[mid][e]-1 ? 0 : idxe+1);
}
// start_t에서 시작하는 그래프
Time nxt;
auto [et1, ea1, eb1] = dist[mid][e][idxe];
ll rest=ea1*mid_r.fi+eb1+(mid_t.fi-mid_r.fi);
nxt=Time(start_t.fi, sa*ea1, rest-sa*ea1*start_t.fi);
if(idx==0 || pll(tmpt[idx-1].a, tmpt[idx-1].b)!=pll(nxt.a, nxt.b)) tmpt[idx++]=nxt;
if(sa==0) continue;
// et에서 시작하는 그래프
bool start_flag=true;
int stj=(idxe+1)%siz[mid][e];
for(int j=stj;;j=(j==siz[mid][e]-1 ? 0 : j+1)){
if(Sdist(mid_r.fi, dist[mid][e][j].t)>Sdist(mid_r.fi, mid_r.se)) break;
if(!start_flag && j==stj) break;
start_flag=false;
auto [net, nea, neb] = dist[mid][e][j];
ll nxtt=dist[mid][e][j].t+(dist[mid][e][j].t<mid_r.fi ? S : 0)+(mid_t.fi-mid_r.fi)-sb;
nxt=Time(nxtt, sa*nea, nea*dist[mid][e][j].t+neb+(dist[mid][e][j].t<mid_r.fi ? S : 0)+(mid_t.fi-mid_r.fi)-sa*nea*nxtt);
if(idx==0 || pll(tmpt[idx-1].a, tmpt[idx-1].b)!=pll(nxt.a, nxt.b)) tmpt[idx++]=nxt;
}
}
sztmp=idx;
}
void add2(ll st, pll nxt){
if(szttmp==0 || ttmpt[szttmp-1].a!=nxt.fi || ttmpt[szttmp-1].b!=nxt.se) ttmpt[szttmp++]=Time(st, nxt.fi, nxt.se);
}
void add1(ll st, ll et, pll f, pll g){
if(f.fi==g.fi){
pll nxt=pll(f.fi, min(f.se, g.se));
add2(st, nxt);
return;
}
if(f.fi==0) swap(f, g); // now f.fi==1 and g.fi==0
ll mt=g.se-f.se;
if(mt>st){
pll nxt=f;
add2(st, nxt);
}
if(mt<=et){
pll nxt=g;
add2(st, nxt);
}
}
void upd(int s, int e){
if(sztmp==0) return;
if(siz[s][e]==0){
for(int i=0;i<sztmp;i++) dist[s][e][i]=tmpt[i];
siz[s][e]=sztmp;
return;
}
szttmp=0;
int cur1=0, cur2=0;
while(true){
ll s1=dist[s][e][cur1].t, s2=tmpt[cur2].t;
ll e1=(cur1==siz[s][e]-1 ? S-1 : dist[s][e][cur1+1].t-1), e2=(cur2==sztmp-1 ? S-1 : tmpt[cur2+1].t-1);
add1(max(s1, s2), min(e1, e2), pll(dist[s][e][cur1].a, dist[s][e][cur1].b), pll(tmpt[cur2].a, tmpt[cur2].b));
if(cur1==siz[s][e]-1 && cur2==sztmp-1) break;
if(e1<e2) cur1++;
if(e1==e2) cur1++, cur2++;
if(e1>e2) cur2++;
}
siz[s][e]=szttmp;
for(int i=0;i<szttmp;i++) dist[s][e][i]=ttmpt[i];
}
void floyd_warshall(){
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++){
if(adj[i][j]==pll()) siz[i][j]=0;
else{
siz[i][j]=2;
dist[i][j][0]=Time(0, 1, adj[i][j].fi);
dist[i][j][1]=Time(adj[i][j].se-adj[i][j].fi+1, 0, S+adj[i][j].fi);
}
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
for(int k=1;k<=N;k++){
if(j!=i && k!=i){
mrg(j, k, i);
upd(j, k);
}
}
}
}
}
vector <ll> solv_query(){
vector <ll> ans;
ans.resize(Q);
for(int i=0;i<Q;i++){
ll s=qry[i][0], e=qry[i][1], t=qry[i][2];
int idx=lower_bound(dist[s][e], dist[s][e]+siz[s][e], Time(t, 2, 0), [](Time a, Time b){return a.t!=b.t ? a.t<b.t : a.a<b.a;})-dist[s][e]-1;
ans[i]=dist[s][e][idx].a*t+dist[s][e][idx].b-t;
}
//for(int i=0;i<Q;i++) cout << ans[i] << '\n';
return ans;
}
std::vector<long long> calculate_necessary_time(
int n, int m, long long s, 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) {
N=n; M=m; S=s; Q=q;
for(int i=0;i<m;i++){
int s, e;
ll x, l;
s=A[i], e=B[i], x=L[i], l=C[i];
s++; e++;
adj[s][e]=pll(x, l);
adj[e][s]=pll(x, l);
}
for(int i=0;i<q;i++){
qry[i][0]=U[i], qry[i][1]=V[i], qry[i][2]=T[i];
qry[i][0]++, qry[i][1]++;
}
floyd_warshall();
return solv_query();
}
Compilation message
escape_route.cpp: In function 'void mrg(int, int, int)':
escape_route.cpp:56:9: warning: unused variable 'idxs' [-Wunused-variable]
56 | int idxs=0, idxe=0, idx=0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
74576 KB |
Output is correct |
| 2 |
Runtime error |
70 ms |
74576 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
277 ms |
300912 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
74576 KB |
Output is correct |
| 2 |
Runtime error |
70 ms |
74576 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
74576 KB |
Output is correct |
| 2 |
Runtime error |
70 ms |
74576 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
74576 KB |
Output is correct |
| 2 |
Runtime error |
70 ms |
74576 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
