Submission #386306

#	Time	Username	Problem	Language	Result	Execution time	Memory
386306		model_code	Escape Route (JOI21_escape_route)	C++17	100 / 100	2077 ms	278024 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
const long long inf = 1000000000000000000;

#define N_MAX 90
#define M_MAX (N_MAX * (N_MAX - 1) / 2)
#define Q_MAX 3000000

class Path {
public:
    long long l, c, d;
    Path(): l(inf * 2), c(0), d(-inf * 2) {}
    Path(long long _l, long long _c): l(_l), c(_c), d(_c - _l) {}
};

int n, m;
long long s;
Path ps[N_MAX][N_MAX];
tuple<int, int, Path> pl[M_MAX];
long long reach[N_MAX][N_MAX];
long long from0[N_MAX][N_MAX];
long long latest_first[N_MAX][M_MAX * 2];
long long latest_second[M_MAX * 2][N_MAX];
vector<pair<long long, int>> query[N_MAX][N_MAX];
int ql[Q_MAX];
vector<long long> answer;

long long require_time(Path p, long long t) {
    t = t % s;
    if(t <= p.d) {
        return p.l;
    } else {
        return s + p.l - t;
    }
}
long long require_time_oneday(Path p, long long t) {
    if(t <= p.d) {
        return p.l;
    } else {
        return inf;
    }
}
long long require_time_oneday_reverse(Path p, long long t) {
    if(t < p.l) {
        return inf;
    } else if(t > p.c) {
        return t - p.d;
    } else {
        return p.l;
    }
}

void prepare_overday_reverse(int x) {
    vector<long long> z(n, -1);
    vector<bool> un(n, true);
    int now = x;
    z[x] = s - 1;
    while(now >= 0) {
        un[now] = false;
        long long nt = z[now];
        int next = -1;
        long long current = -1;
        rep(i, n) {
            if(un[i]) {
                z[i] = max(z[i], nt - require_time_oneday_reverse(ps[now][i], nt));
                if(current < z[i]) {
                    current = z[i];
                    next = i;
                }
            }
        }
        now = next;
    }
    rep(i, n) {
        reach[i][x] = z[i];
    }
}
void prepare_overday(int x) {
    vector<long long> z(n, inf);
    vector<bool> un(n, true);
    int now = x;
    z[x] = 0;
    while(now >= 0) {
        un[now] = false;
        long long nt = z[now];
        int next = -1;
        long long current = inf;
        rep(i, n) {
            if(un[i]) {
                z[i] = min(z[i], nt + require_time(ps[now][i], nt));
                if(current > z[i]) {
                    current = z[i];
                    next = i;
                }
            }
        }
        now = next;
    }
    rep(i, n) {
        from0[i][x] = z[i];
    }
}
void prepare_overday() {
    rep(i, n) {
        prepare_overday_reverse(i);
        prepare_overday(i);
    }
}
void prepare_oneday_reverse(int x, long long t, int w) {
    vector<long long> z(n, -1);
    vector<bool> un(n, true);
    int now = w;
    z[w] = t;
    while(now >= 0) {
        un[now] = false;
        long long nt = z[now];
        int next = -1;
        long long current = -1;
        rep(i, n) {
            if(un[i]) {
                z[i] = max(z[i], nt - require_time_oneday_reverse(ps[now][i], nt));
                if(current < z[i]) {
                    current = z[i];
                    next = i;
                }
            }
        }
        now = next;
    }
    rep(i, n) {
        latest_first[i][x] = z[i];
    }
}
void prepare_oneday(int x, long long t, int w) {
    vector<long long> z(n, inf);
    vector<bool> un(n, true);
    int now = w;
    z[w] = t;
    while(now >= 0) {
        un[now] = false;
        long long nt = z[now];
        int next = -1;
        long long current = inf;
        rep(i, n) {
            if(un[i]) {
                z[i] = min(z[i], nt + require_time_oneday(ps[now][i], nt));
                if(current > z[i]) {
                    current = z[i];
                    next = i;
                }
            }
        }
        now = next;
    }
    rep(i, n) {
        latest_second[x][i] = z[i];
    }
}
void prepare_oneday() {
    rep(i, m) {
        prepare_oneday_reverse(i * 2, get<2>(pl[i]).c, get<0>(pl[i]));
        prepare_oneday_reverse(i * 2 + 1, get<2>(pl[i]).c, get<1>(pl[i]));
        prepare_oneday(i * 2, get<2>(pl[i]).c, get<0>(pl[i]));
        prepare_oneday(i * 2 + 1, get<2>(pl[i]).c, get<1>(pl[i]));
    }
}
void prepare() {
    prepare_overday();
    prepare_oneday();
}

void solve_overday(int u, int v) {
    vector<pair<long long, long long>> w;
    rep(i, n) {
        if(reach[u][i] >= 0) {
            w.push_back(make_pair(reach[u][i], from0[v][i]));
        }
    }
    for(auto i: query[u][v]) {
        w.push_back(make_pair(i.first, i.second - inf));
    }
    sort(w.begin(), w.end(), greater<pair<long long, long long>>());
    long long now = inf;
    for(auto i: w) {
        if(i.second < 0) {
            answer[i.second + inf] = min(answer[i.second + inf], s - i.first + now);
        } else {
            now = min(now, i.second);
        }
    }
    for(auto i: w) {
        if(i.second < 0) {
            answer[i.second + inf] = min(answer[i.second + inf], s * 2 - i.first + now);
        }
    }
}
void solve_oneday(int u) {
    vector<pair<long long, long long>> w;
    rep(i, m * 2) {
        if(latest_first[u][i] >= 0) {
            w.push_back(make_pair(latest_first[u][i], i));
        }
    }
    rep(i, n) {
        for(auto j: query[u][i]) {
            w.push_back(make_pair(j.first, j.second - inf));
        }
    }
    sort(w.begin(), w.end(), greater<pair<long long, long long>>());
    vector<long long> now(n, inf);
    for(auto i: w) {
        if(i.second < 0) {
            int idx = i.second + inf;
            answer[idx] = min(answer[idx], now[ql[idx]]);
        } else {
            rep(j, n) {
                now[j] = min(now[j], latest_second[i.second][j] - i.first);
            }
        }
    }
    for(auto i: w) {
        if(i.second < 0) {
            int idx = i.second + inf;
            answer[idx] = min(answer[idx], s - i.first + now[ql[idx]]);
        }
    }
}
void solve(int q) {
    answer.resize(q, inf);
    rep(i, n) {
        rep(j, n) {
            if(i != j) {
                solve_overday(i, j);
            }
        }
    }
    rep(i, n) {
        solve_oneday(i);
    }
}

vector<long long> calculate_necessary_time(
    int N, int M, long long S, int Q, vector<int> A, vector<int> B,
    vector<long long> L, vector<long long> C, vector<int> U,
    vector<int> V, vector<long long> T) {
    n = N;
    m = M;
    s = S;
    rep(i, m) {
        Path p(L[i], C[i]);
        ps[A[i]][B[i]] = p;
        ps[B[i]][A[i]] = p;
        pl[i] = make_tuple(A[i], B[i], p);
    }
    rep(i, Q) {
        query[U[i]][V[i]].push_back(make_pair(T[i], i));
        ql[i] = V[i];
    }
    prepare();
    solve(Q);
    return answer;
}

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