Submission #1081979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081979		azberjibiou	Escape Route (JOI21_escape_route)	C++17	70 / 100	9122 ms	1437048 KiB

escape_route

#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=100;
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)%S+S)%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;
        for(int j=(idxe+1)%siz[mid][e];;j=(j+1)%siz[mid][e]){
            if(Sdist(mid_r.fi, dist[mid][e][j].t)>Sdist(mid_r.fi, mid_r.se)) break;
            if(!start_flag && j==(idxe+1)%siz[mid][e]) 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;
    
    bool p=false;
    if(p){
        printf("MERGE(%d %d %d)\n", s, e, mid);
        for(int i=0;i<siz[s][mid];i++) printf("(%lld %lld %lld) ", dist[s][mid][i].t, dist[s][mid][i].a, dist[s][mid][i].b);
        printf("\n");
        for(int i=0;i<siz[mid][e];i++) printf("(%lld %lld %lld) ", dist[mid][e][i].t, dist[mid][e][i].a, dist[mid][e][i].b);
        printf("\n");
        for(int i=0;i<sztmp;i++){
            printf("(%lld %lld %lld) ", tmpt[i].t, tmpt[i].a, tmpt[i].b);
        }
        printf("\n");
    }
}
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){
    bool p=false;
    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;
        if(p){
            printf("s=%d, e=%d\n", s, e);
            for(int i=0;i<siz[s][e];i++) printf("(%lld %lld %lld) ", dist[s][e][i].t, dist[s][e][i].a, dist[s][e][i].b);
            printf("\n");
        }
        
        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(p) printf("add1(%lld %lld (%lld, %lld) (%lld %lld)) ", max(s1, s2), min(e1, e2), dist[s][e][cur1].a, dist[s][e][cur1].b, tmpt[cur2].a, tmpt[cur2].b);
        if(p) printf("\n");
        if(cur1==siz[s][e]-1 && cur2==sztmp-1) break;
        if(e1<e2) cur1++;
        if(e1==e2) cur1++, cur2++;
        if(e1>e2) cur2++;
        if(p) printf("cur1=%d, cur2=%d\n", cur1, cur2);
    }
    siz[s][e]=szttmp;
    for(int i=0;i<szttmp;i++) dist[s][e][i]=ttmpt[i];
    if(p){
        printf("s=%d, e=%d\n", s, e);
        for(int i=0;i<siz[s][e];i++) printf("(%lld %lld %lld) ", dist[s][e][i].t, dist[s][e][i].a, dist[s][e][i].b);
        printf("\n");
    }
    
}
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 (stderr)

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;
      |         ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30