Submission #933880

#	Time	Username	Problem	Language	Result	Execution time	Memory
933880		boris_mihov	Escape Route (JOI21_escape_route)	C++17	70 / 100	9051 ms	269356 KiB

escape_route

#include "escape_route.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 100;
const llong INF = 1e18;
const int INTINF = 1e9;

int n, m, q;
llong s;

struct Edge
{   
    llong w, l;
    Edge()
    {
        w = 1;
        l = 0;
    }

    Edge(llong _w, llong _l)
    {
        w = _w;
        l = _l;
    }
};

struct Query
{
    int u, v;
    llong time;
    int idx;

    friend bool operator < (const Query &a, const Query&b)
    {
        return a.u < b.u || (a.u == b.u && a.time < b.time);
    }
};

Edge e[MAXN][MAXN];
std::vector <Query> queries;
std::pair <int,llong> days[MAXN][MAXN];
llong zeroTime[MAXN][MAXN];
llong queryDist[MAXN];
int dijkstraPar[MAXN];
bool vis[MAXN];

void runDijkstra(int node, llong time, llong dist[], bool shouldType)
{
    // std::cout << "run dijkstra: " << node << ' ' << time << '\n';
    std::priority_queue <std::pair <llong,int>> pq;
    std::fill(dijkstraPar, dijkstraPar + n, -1);
    std::fill(dist, dist + n, INF);
    std::fill(vis, vis + n, false);
    dist[node] = time;
 
    pq.push({time, node});
    while (pq.size())
    {
        auto [currDist, node] = pq.top();
        pq.pop();
 
        if (vis[node])
        {
            continue;
        }
 
        vis[node] = true;
        for (int u = 0 ; u < n ; ++u)
        {
            if (dist[node] + e[node][u].w <= e[node][u].l && dist[u] > dist[node] + e[node][u].w)
            {
                dijkstraPar[u] = node;
                dist[u] = dist[node] + e[node][u].w;
                pq.push({-dist[u], u});
            }
        }
    }
 
    if (!shouldType) return;
    for (int i = 0 ; i < n ; ++i)
    {
        if (dist[i] != INF) days[node][i] = {0, dist[i]};
        else
        {
            days[node][i] = {INTINF, INF};
        }
    }
}

std::vector <llong> calculate_necessary_time(int N, int M, long long S, int Q, std::vector <int> A, std::vector <int> B, std::vector <llong> L, std::vector <llong> C, std::vector <int> U, std::vector <int> V, std::vector <llong> T)
{
    // std::cout << "call\n" << std::flush;
    n = N;
    m = M;
    s = S;
    q = Q;

    for (int i = 0 ; i < m ; ++i)
    {
        e[A[i]][B[i]] = {L[i], C[i]};
        e[B[i]][A[i]] = {L[i], C[i]};
    }

    for (int i = 0 ; i < q ; ++i)
    {
        queries.push_back({U[i], V[i], T[i], i});
    }

    for (int i = 0 ; i < n ; ++i)
    {
        runDijkstra(i, 0, zeroTime[i], true);
    }

    for (int k = 0 ; k < n ; ++k)
    {
        for (int i = 0 ; i < n ; ++i)
        {
            for (int j = 0 ; j < n ; ++j)
            {
                if (i == j || i == k || j == k)
                {
                    continue;
                }       

                if (days[i][k].second == INF || days[k][j].second == INF)
                {
                    continue;
                }

                std::pair <int,llong> currTry;
                currTry.first = days[i][k].first + days[k][j].first + 1;
                currTry.second = days[k][j].second;
            
                // std::cout << "current try: " << i << ' ' << j << ' ' << k << ' ' << currTry.first << ' ' << currTry.second << ' ' << days[i][j].first << ' ' << days[i][j].second << '\n';
                if (currTry.first < days[i][j].first || (currTry.first == days[i][j].first && currTry.second < days[i][j].second))
                {
                    days[i][j] = currTry;
                    // if (i == 0 && j == 3) std::cout << "dist: " << i << ' ' << j << " = " << dist[i][j].first << ' ' << dist[i]
                }
            }
        }
    }

    std::vector <llong> res(q);
    std::sort(queries.begin(), queries.end());
    int lastNode = -1;
    llong toTime = 0;
    llong lastT = 0;

    for (int i = 0 ; i < q ; ++i)
    {
        // std::cout << "new query: " << i << "\n\n";
        int u = queries[i].u;
        int v = queries[i].v;
        llong t = queries[i].time;
        int idx = queries[i].idx;

        if (u != lastNode || t > toTime)
        {
            toTime = INF;
            runDijkstra(u, t, queryDist, false);
            for (int i = 0 ; i < n ; ++i)
            {
                if (dijkstraPar[i] != -1) toTime = std::min(toTime, e[dijkstraPar[i]][i].l - e[dijkstraPar[i]][i].w - queryDist[dijkstraPar[i]] + t);
            }

            lastNode = u;
            lastT = t;
        }

        if (queryDist[v] != INF)
        {
            res[idx] = queryDist[v] - lastT;
            continue;
        }

        std::pair <int,llong> answer = {INTINF, INF};
        for (int node = 0 ; node < n ; ++node)
        {
            if (queryDist[node] != INF)
            {
                // std::cout << "here: " << node << ' ' << v << ' ' << days[node][v].first << ' ' << days[node][v].second << '\n';
                if (answer.first > days[node][v].first || (answer.first == days[node][v].first && answer.second > days[node][v].second))
                {
                    answer = days[node][v];
                }
            }
        }

        res[idx] = 1LL * (1 + answer.first) * s + answer.second - t;
    }

    return res;
}

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