oj.uz

Submission #933880

# Submission time Handle Problem Language Result Execution time Memory
933880 2024-02-26T12:56:28 Z boris_mihov Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 269356 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65112 KB Output is correct
2 Correct 11 ms 65112 KB Output is correct
3 Correct 19 ms 65112 KB Output is correct
4 Correct 11 ms 65116 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 178012 KB Output is correct
2 Correct 628 ms 244080 KB Output is correct
3 Correct 582 ms 225472 KB Output is correct
4 Correct 650 ms 254652 KB Output is correct
5 Correct 641 ms 253436 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct
7 Correct 559 ms 224148 KB Output is correct
8 Correct 676 ms 266216 KB Output is correct
9 Correct 552 ms 214000 KB Output is correct
10 Correct 629 ms 253520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65112 KB Output is correct
2 Correct 11 ms 65112 KB Output is correct
3 Correct 19 ms 65112 KB Output is correct
4 Correct 11 ms 65116 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct
7 Correct 540 ms 178012 KB Output is correct
8 Correct 628 ms 244080 KB Output is correct
9 Correct 582 ms 225472 KB Output is correct
10 Correct 650 ms 254652 KB Output is correct
11 Correct 641 ms 253436 KB Output is correct
12 Correct 11 ms 65116 KB Output is correct
13 Correct 559 ms 224148 KB Output is correct
14 Correct 676 ms 266216 KB Output is correct
15 Correct 552 ms 214000 KB Output is correct
16 Correct 629 ms 253520 KB Output is correct
17 Correct 768 ms 224164 KB Output is correct
18 Correct 849 ms 223716 KB Output is correct
19 Correct 971 ms 247640 KB Output is correct
20 Correct 637 ms 227576 KB Output is correct
21 Correct 979 ms 255616 KB Output is correct
22 Correct 987 ms 255552 KB Output is correct
23 Correct 616 ms 226604 KB Output is correct
24 Correct 706 ms 269212 KB Output is correct
25 Correct 762 ms 214016 KB Output is correct
26 Correct 1022 ms 255888 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65112 KB Output is correct
2 Correct 11 ms 65112 KB Output is correct
3 Correct 19 ms 65112 KB Output is correct
4 Correct 11 ms 65116 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct
7 Correct 540 ms 178012 KB Output is correct
8 Correct 628 ms 244080 KB Output is correct
9 Correct 582 ms 225472 KB Output is correct
10 Correct 650 ms 254652 KB Output is correct
11 Correct 641 ms 253436 KB Output is correct
12 Correct 11 ms 65116 KB Output is correct
13 Correct 559 ms 224148 KB Output is correct
14 Correct 676 ms 266216 KB Output is correct
15 Correct 552 ms 214000 KB Output is correct
16 Correct 629 ms 253520 KB Output is correct
17 Correct 768 ms 224164 KB Output is correct
18 Correct 849 ms 223716 KB Output is correct
19 Correct 971 ms 247640 KB Output is correct
20 Correct 637 ms 227576 KB Output is correct
21 Correct 979 ms 255616 KB Output is correct
22 Correct 987 ms 255552 KB Output is correct
23 Correct 616 ms 226604 KB Output is correct
24 Correct 706 ms 269212 KB Output is correct
25 Correct 762 ms 214016 KB Output is correct
26 Correct 1022 ms 255888 KB Output is correct
27 Correct 1817 ms 223736 KB Output is correct
28 Correct 2381 ms 222588 KB Output is correct
29 Correct 2840 ms 246072 KB Output is correct
30 Correct 762 ms 227124 KB Output is correct
31 Correct 3048 ms 255080 KB Output is correct
32 Correct 3052 ms 256660 KB Output is correct
33 Correct 741 ms 269356 KB Output is correct
34 Correct 1815 ms 214988 KB Output is correct
35 Correct 2950 ms 256888 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65112 KB Output is correct
2 Correct 11 ms 65112 KB Output is correct
3 Correct 19 ms 65112 KB Output is correct
4 Correct 11 ms 65116 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 10 ms 65116 KB Output is correct
7 Correct 540 ms 178012 KB Output is correct
8 Correct 628 ms 244080 KB Output is correct
9 Correct 582 ms 225472 KB Output is correct
10 Correct 650 ms 254652 KB Output is correct
11 Correct 641 ms 253436 KB Output is correct
12 Correct 11 ms 65116 KB Output is correct
13 Correct 559 ms 224148 KB Output is correct
14 Correct 676 ms 266216 KB Output is correct
15 Correct 552 ms 214000 KB Output is correct
16 Correct 629 ms 253520 KB Output is correct
17 Correct 768 ms 224164 KB Output is correct
18 Correct 849 ms 223716 KB Output is correct
19 Correct 971 ms 247640 KB Output is correct
20 Correct 637 ms 227576 KB Output is correct
21 Correct 979 ms 255616 KB Output is correct
22 Correct 987 ms 255552 KB Output is correct
23 Correct 616 ms 226604 KB Output is correct
24 Correct 706 ms 269212 KB Output is correct
25 Correct 762 ms 214016 KB Output is correct
26 Correct 1022 ms 255888 KB Output is correct
27 Correct 1817 ms 223736 KB Output is correct
28 Correct 2381 ms 222588 KB Output is correct
29 Correct 2840 ms 246072 KB Output is correct
30 Correct 762 ms 227124 KB Output is correct
31 Correct 3048 ms 255080 KB Output is correct
32 Correct 3052 ms 256660 KB Output is correct
33 Correct 741 ms 269356 KB Output is correct
34 Correct 1815 ms 214988 KB Output is correct
35 Correct 2950 ms 256888 KB Output is correct
36 Execution timed out 9051 ms 193284 KB Time limit exceeded
37 Halted 0 ms 0 KB -