Submission #713444

#	Time	Username	Problem	Language	Result	Execution time	Memory
713444		PixelCat	Escape Route (JOI21_escape_route)	C++17	0 / 100	9059 ms	470672 KiB

escape_route

#include "escape_route.h"

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
#define MOD (int)(1000000007)
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 100;
const int MAXQ = 3000030;
const int INF = 8e18;

struct Edge {
    int c, l;  // close time, length
};
struct Query {
    int u, v, t, id;
};
struct Path {
    int s, t, d, l;
    bool operator<(const Path &p) const {
        return l < p.l;
    }
};

int N, M, S, Q;
Edge adj[MAXN][MAXN];
pii owo[MAXN][MAXN];
int vis[MAXN];
int dist[MAXN][MAXN];
int rem[MAXN][MAXN];
bool ok[MAXN][MAXN];
vector<Query> qry;
vector<int> ans;

// starting from time=0
void meow(int s) {
    For(i, 0, N - 1) {
        owo[s][i] = pii(INF, INF);
        vis[i] = 0;
    }
    owo[s][s] = pii(0, 0);
    For(_, 0, N - 1) {
        int idx = -1;
        pii mn(INF, INF);
        For(i, 0, N - 1) if(!vis[i]) {
            if(owo[s][i] < mn) {
                mn = owo[s][i];
                idx = i;
            }
        }
        assert(idx >= 0);
        vis[idx] = 1;
        For(i, 0, N - 1) if(adj[idx][i].l > 0) {
            pii nt(mn.first, mn.second + adj[idx][i].l);
            if(nt.second > adj[idx][i].c) {
                nt = pii(mn.first + 1, adj[idx][i].l);
            }
            owo[s][i] = min(owo[s][i], nt);
        }
    }
}

int nya() {
    int u, v, t;
    u = qry.back().u; v = qry.back().v; t = qry.back().t;
    int pos = qry.back().id;
    qry.pop_back();
    // cout << "========\n";
    // For(j, 0, N - 1) For(i, 0, N - 1) {
    //     if(dist[j][i] >= INF) cout << "-1";
    //     else cout << dist[j][i];
    //     cout << " \n"[i == N - 1];
    // }
    // cout << "========\n";
    if(dist[u][v] != INF) return ans[pos] = dist[u][v];
    int res = INF;
    For(i, 0, N - 1) if(dist[u][i] != INF) {
        auto tm = owo[i][v];
        res = min(res, S * (tm.first + 1) + tm.second - t);
    }
    // cout << "-> " << u << " " << v << " " << t << " " << pos << "\n";
    return ans[pos] = res;
}

std::vector<long long> calculate_necessary_time(
    int32_t _N, int32_t _M, long long _S, int32_t _Q, std::vector<int32_t> A, std::vector<int32_t> B,
    std::vector<long long> L, std::vector<long long> C, std::vector<int32_t> U,
    std::vector<int32_t> V, std::vector<long long> T) {
    N = _N; M = _M; S = _S; Q = _Q;
    For(i, 0, N - 1) For(j, 0, N - 1) {
        adj[i][j] = {-1, -1};
        dist[i][j] = (i == j ? 0 : INF);
        rem[i][j] = (i == j ? INF : -INF);
        ok[i][j] = 0;
    }
    priority_queue<Path> pq;
    For(i, 0, M - 1) {
        int a = A[i];
        int b = B[i];
        int l = L[i];
        int c = C[i];
        adj[a][b] = adj[b][a] = {c, l};
        pq.emplace((Path){a, b, l, c - l});
        pq.emplace((Path){b, a, l, c - l});
    }
    For(i, 0, N - 1) meow(i);
    For(i, 0, Q - 1) {
        qry.eb((Query){U[i], V[i], T[i], i});
    }
    ans.resize(Q);
    sort(all(qry), [&](auto &a, auto &b) {
        return a.t < b.t;
    });
    while(!pq.empty()) {
        Path p = pq.top(); pq.pop();
        // cout << p.s << " " << p.t << " " << p.d << " " << p.l << "\n";
        
        // expired queries
        while(sz(qry) && qry.back().t > p.l) {
            nya();
        }

        if(p.d < dist[p.s][p.t]) {
            dist[p.s][p.t] = p.d;
            rem[p.s][p.t] = p.l;
        }
        // relax
        For(i, 0, N - 1) if(dist[p.t][i] < INF) {
            int nd = p.d + dist[p.t][i];
            int nr = min(p.l, rem[p.t][i] - p.d);
            if(nr >= p.l) {
                if(nd < dist[p.s][i]) {
                    dist[p.s][i] = nd;
                    rem[p.s][i] = nr;
                }
            } else if(nr >= 0 && nd < dist[p.s][i]) {
                pq.emplace((Path){p.s, i, nd, nr});
            }
        }
        For(i, 0, N - 1) if(dist[i][p.s] < INF) {
            int nd = p.d + dist[i][p.s];
            int nr = min(rem[i][p.s], p.l - dist[i][p.s]);
            if(nr >= 0 && nd < dist[i][p.t]) {
                pq.emplace((Path){i, p.t, nd, nr});
            }
        }
    }
    while(sz(qry)) nya();
    return ans;
}

/*

g++ -std=c++14 -O2 -fsigned-char -o grader grader.cpp escape_route.cpp & grader.exe < input.txt > output.txt 2> error.txt

*/

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