oj.uz

Submission #1081979

# Submission time Handle Problem Language Result Execution time Memory
1081979 2024-08-30T13:47:22 Z azberjibiou Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 1437048 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 1239632 KB Output is correct
2 Correct 504 ms 1239636 KB Output is correct
3 Correct 505 ms 1239632 KB Output is correct
4 Correct 464 ms 1239784 KB Output is correct
5 Correct 542 ms 1239616 KB Output is correct
6 Correct 465 ms 1239780 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 1393972 KB Output is correct
2 Correct 1136 ms 1416920 KB Output is correct
3 Correct 777 ms 1398004 KB Output is correct
4 Correct 1234 ms 1425272 KB Output is correct
5 Correct 1223 ms 1424908 KB Output is correct
6 Correct 473 ms 1239636 KB Output is correct
7 Correct 783 ms 1396148 KB Output is correct
8 Correct 703 ms 1437048 KB Output is correct
9 Correct 1000 ms 1385720 KB Output is correct
10 Correct 1186 ms 1424312 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 1239632 KB Output is correct
2 Correct 504 ms 1239636 KB Output is correct
3 Correct 505 ms 1239632 KB Output is correct
4 Correct 464 ms 1239784 KB Output is correct
5 Correct 542 ms 1239616 KB Output is correct
6 Correct 465 ms 1239780 KB Output is correct
7 Correct 1183 ms 1393972 KB Output is correct
8 Correct 1136 ms 1416920 KB Output is correct
9 Correct 777 ms 1398004 KB Output is correct
10 Correct 1234 ms 1425272 KB Output is correct
11 Correct 1223 ms 1424908 KB Output is correct
12 Correct 473 ms 1239636 KB Output is correct
13 Correct 783 ms 1396148 KB Output is correct
14 Correct 703 ms 1437048 KB Output is correct
15 Correct 1000 ms 1385720 KB Output is correct
16 Correct 1186 ms 1424312 KB Output is correct
17 Correct 1208 ms 1396448 KB Output is correct
18 Correct 1376 ms 1394668 KB Output is correct
19 Correct 1203 ms 1417716 KB Output is correct
20 Correct 776 ms 1399796 KB Output is correct
21 Correct 1321 ms 1424960 KB Output is correct
22 Correct 1363 ms 1417760 KB Output is correct
23 Correct 786 ms 1393008 KB Output is correct
24 Correct 780 ms 1416984 KB Output is correct
25 Correct 1154 ms 1380252 KB Output is correct
26 Correct 1367 ms 1406700 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 1239632 KB Output is correct
2 Correct 504 ms 1239636 KB Output is correct
3 Correct 505 ms 1239632 KB Output is correct
4 Correct 464 ms 1239784 KB Output is correct
5 Correct 542 ms 1239616 KB Output is correct
6 Correct 465 ms 1239780 KB Output is correct
7 Correct 1183 ms 1393972 KB Output is correct
8 Correct 1136 ms 1416920 KB Output is correct
9 Correct 777 ms 1398004 KB Output is correct
10 Correct 1234 ms 1425272 KB Output is correct
11 Correct 1223 ms 1424908 KB Output is correct
12 Correct 473 ms 1239636 KB Output is correct
13 Correct 783 ms 1396148 KB Output is correct
14 Correct 703 ms 1437048 KB Output is correct
15 Correct 1000 ms 1385720 KB Output is correct
16 Correct 1186 ms 1424312 KB Output is correct
17 Correct 1208 ms 1396448 KB Output is correct
18 Correct 1376 ms 1394668 KB Output is correct
19 Correct 1203 ms 1417716 KB Output is correct
20 Correct 776 ms 1399796 KB Output is correct
21 Correct 1321 ms 1424960 KB Output is correct
22 Correct 1363 ms 1417760 KB Output is correct
23 Correct 786 ms 1393008 KB Output is correct
24 Correct 780 ms 1416984 KB Output is correct
25 Correct 1154 ms 1380252 KB Output is correct
26 Correct 1367 ms 1406700 KB Output is correct
27 Correct 2851 ms 1387828 KB Output is correct
28 Correct 3534 ms 1386048 KB Output is correct
29 Correct 3684 ms 1410324 KB Output is correct
30 Correct 967 ms 1394072 KB Output is correct
31 Correct 3711 ms 1408576 KB Output is correct
32 Correct 3717 ms 1409888 KB Output is correct
33 Correct 776 ms 1419212 KB Output is correct
34 Correct 2730 ms 1381940 KB Output is correct
35 Correct 3698 ms 1408976 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 1239632 KB Output is correct
2 Correct 504 ms 1239636 KB Output is correct
3 Correct 505 ms 1239632 KB Output is correct
4 Correct 464 ms 1239784 KB Output is correct
5 Correct 542 ms 1239616 KB Output is correct
6 Correct 465 ms 1239780 KB Output is correct
7 Correct 1183 ms 1393972 KB Output is correct
8 Correct 1136 ms 1416920 KB Output is correct
9 Correct 777 ms 1398004 KB Output is correct
10 Correct 1234 ms 1425272 KB Output is correct
11 Correct 1223 ms 1424908 KB Output is correct
12 Correct 473 ms 1239636 KB Output is correct
13 Correct 783 ms 1396148 KB Output is correct
14 Correct 703 ms 1437048 KB Output is correct
15 Correct 1000 ms 1385720 KB Output is correct
16 Correct 1186 ms 1424312 KB Output is correct
17 Correct 1208 ms 1396448 KB Output is correct
18 Correct 1376 ms 1394668 KB Output is correct
19 Correct 1203 ms 1417716 KB Output is correct
20 Correct 776 ms 1399796 KB Output is correct
21 Correct 1321 ms 1424960 KB Output is correct
22 Correct 1363 ms 1417760 KB Output is correct
23 Correct 786 ms 1393008 KB Output is correct
24 Correct 780 ms 1416984 KB Output is correct
25 Correct 1154 ms 1380252 KB Output is correct
26 Correct 1367 ms 1406700 KB Output is correct
27 Correct 2851 ms 1387828 KB Output is correct
28 Correct 3534 ms 1386048 KB Output is correct
29 Correct 3684 ms 1410324 KB Output is correct
30 Correct 967 ms 1394072 KB Output is correct
31 Correct 3711 ms 1408576 KB Output is correct
32 Correct 3717 ms 1409888 KB Output is correct
33 Correct 776 ms 1419212 KB Output is correct
34 Correct 2730 ms 1381940 KB Output is correct
35 Correct 3698 ms 1408976 KB Output is correct
36 Execution timed out 9122 ms 1338656 KB Time limit exceeded
37 Halted 0 ms 0 KB -