Submission #709746

#	Time	Username	Problem	Language	Result	Execution time	Memory
709746		PixelCat	Escape Route (JOI21_escape_route)	C++17	5 / 100	9056 ms	112076 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 INF = 8e18;

struct Edge {
    int c, l;  // close time, length
};

int N, M, S, Q;
Edge adj[MAXN][MAXN];
pii owo[MAXN][MAXN];
int vis[MAXN];
int dist[MAXN];

// 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, int v, int t) {
    For(i, 0, N - 1) {
        dist[i] = INF;
        vis[i] = 0;
    }
    dist[u] = t;
    For(_, 0, N - 1) {
        int idx = -1;
        int mn = INF;
        For(i, 0, N - 1) if(!vis[i]) {
            if(dist[i] < mn) {
                mn = dist[i];
                idx = i;
            }
        }
        vis[idx] = 1;
        For(i, 0, N - 1) if(adj[idx][i].l > 0) {
            auto nt = mn + adj[idx][i].l;
            if(nt <= adj[idx][i].c) {
                dist[i] = min(dist[i], nt);
            }
        }
    }
    if(dist[v] != INF) return dist[v] - dist[u];
    int ans = INF;
    For(i, 0, N - 1) if(dist[i] != INF) {
        auto tm = owo[i][v];
        ans = min(ans, S * (tm.first + 1) + tm.second - dist[u]);
    }
    return ans;
}

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};
    }
    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};
    }
    For(i, 0, N - 1) meow(i);
    vector<int> res;
    For(i, 0, Q - 1) {
        res.eb(nya(U[i], V[i], T[i]));
    }
    // cout << res.back() << "\n";
    // For(i, 0, N - 1) For(j, 0, N - 1) {
    //     cout << owo[i][j].first << "+" << owo[i][j].second << " \n"[j == N - 1];
    // }
    return res;
}

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