Submission #933859

#	Time	Username	Problem	Language	Result	Execution time	Memory
933859		boris_mihov	Escape Route (JOI21_escape_route)	C++17	5 / 100	9029 ms	112380 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
{   
    int to;
    llong w, l;
    Edge()
    {
        w = 1;
        l = 0;
    }

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

Edge e[MAXN][MAXN];
std::vector <Edge> g[MAXN];
std::pair <int,llong> days[MAXN][MAXN];
llong zeroTime[MAXN][MAXN];
llong queryDist[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(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 (const auto &[u, w, l] : g[node])
        {
            if (dist[node] + w <= l && dist[u] > dist[node] + w)
            {
                dist[u] = dist[node] + 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)
    {
        g[A[i]].push_back({B[i], L[i], C[i]});
        g[B[i]].push_back({A[i], L[i], C[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);
    for (int i = 0 ; i < q ; ++i)
    {
        // std::cout << "new query: " << i << "\n\n";
        int u = U[i];
        int v = V[i];
        llong t = T[i];
        runDijkstra(u, t, queryDist, false);
        if (queryDist[v] != INF)
        {
            // std::cout << "here: " << queryDist[v] << ' ' << t << '\n';
            res[i] = queryDist[v] - t;
            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[i] = 1LL * (1 + answer.first) * s + answer.second - t;
    }

    return res;
}

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