Submission #617746

#	Time	Username	Problem	Language	Result	Execution time	Memory
617746		qwerasdfzxcl	Escape Route (JOI21_escape_route)	C++17	0 / 100	1006 ms	211992 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const ll INF = 4e18;
struct Edge{
    int v;
    ll l, c;
    Edge(){}
    Edge(int _v, ll _l, ll _c): v(_v), l(_l), c(_c) {}
};
vector<Edge> adj[101];
int n, m, q;
ll MOD, dist0[101][101], ran[101][4040], dist[101][4040][101], par[101], sz[101];
bool visited[101];
 
vector<ll> ans;
 
ll dijkstra(int s, ll t, ll dist[], bool is0){
    fill(dist+1, dist+n+1, INF);
    fill(visited+1, visited+n+1, 0);
    fill(par+1, par+n+1, INF);
 
    dist[s] = t;
    ll ret = INF;
 
    for (int i=1;i<=n;i++){
        ll mn = INF, v = -1;
        for (int j=1;j<=n;j++) if (!visited[j] && mn > dist[j]) mn = dist[j], v = j;
        if (v==-1) break;
 
        visited[v] = 1;
        ret = min(ret, par[v]);
        //printf(" %d %lld\n", v, mn);
 
        for (auto &[nxt, l, c]:adj[v]) if (!visited[nxt]){
            ll nt = mn + l;
            if (mn%MOD > c-l){
                if (!is0) continue;
                nt = (mn/MOD*MOD + MOD) + l;
            }
 
            if (nt < dist[nxt]){
                dist[nxt] = nt;
                if (!is0) par[nxt] = c-l-mn+1;
            }
        }
    }
 
    return ret;
}

struct FUCK{
    int u, v, i;
    ll t;
    FUCK(){}
    FUCK(int _u, int _v, ll _t, int _i): u(_u), v(_v), i(_i), t(_t) {}
    bool operator<(const FUCK &FUUUUUCK) const{
        return tie(u, t) < tie(FUUUUUCK.u, FUUUUUCK.t);
    }
}fuck[3003000];

int fuuck[101];
 
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, MOD = S, q = Q;
    for (int i=0;i<m;i++){
        ++A[i], ++B[i];
 
        adj[A[i]].emplace_back(B[i], L[i], C[i]);
        adj[B[i]].emplace_back(A[i], L[i], C[i]);
    }
 
    for (int i=1;i<=n;i++) dijkstra(i, 0, dist0[i], 1);
    for (int i=1;i<=n;i++){
        int pt = 0;
        ll curt = 0;
        while(true){
            assert(pt<=m+2);
            ran[i][pt] = curt;
            ll tmp = dijkstra(i, curt, dist[i][pt], 0);
 
            ++pt;
            curt += tmp;
            if (curt >= MOD) break;
 
        }
 
        /*if (i==1){
            for (int j=0;j<pt;j++) printf(" %lld", ran[i][j]);
            printf("\n");
        }*/
 
        ran[i][pt] = MOD;
        sz[i] = pt+1;
    }
 
    //printf("  %lld\n", dist[1][0][4]);
 
    for (int i=0;i<q;i++) fuck[i] = FUCK(U[i]+1, V[i]+1, T[i], i);
    sort(fuck, fuck+q);
    ans.resize(q);

    for (int i=0;i<q;i++){
        int u = fuck[i].u;
        int v = fuck[i].v;
        int ii = fuck[i].i;
        ll t = fuck[i].t;

        while(fuuck[u]<sz[u] && ran[u][fuuck[u]] <=  t) fuuck[u]++;
        int pt = fuuck[u] - 1;
        //printf(" %d %d %lld -> %d\n", U[i], V[i], T[i], pt);
        ll ret = dist[u][v][pt] - ran[u][pt];
        for (int j=1;j<=n;j++) if (dist[u][j][pt]<INF){
            ret = min(ret, MOD - t + dist0[j][v]);
        }
        ans[ii] = ret;
    }
 
    return ans;
}

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