oj.uz

Submission #1013192

# Submission time Handle Problem Language Result Execution time Memory
1013192 2024-07-03T09:35:11 Z Unforgettablepl Escape Route (JOI21_escape_route) C++17
100 / 100
 3806 ms 230648 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;

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) {
    vector<vector<tuple<int,int,int>>> adj(N);
    vector<vector<tuple<int,int,int,int>>> sadj(N);
    map<pair<int,int>,int> lookup;
    for(int i=0;i<M;i++){
        lookup[{A[i],B[i]}]=i;
        lookup[{B[i],A[i]}]=i;
        adj[A[i]].emplace_back(B[i],L[i],C[i]);
        adj[B[i]].emplace_back(A[i],L[i],C[i]);
        sadj[A[i]].emplace_back(C[i]-L[i],B[i],L[i],i);
        sadj[B[i]].emplace_back(C[i]-L[i],A[i],L[i],i+M);
    }
    for(int i=0;i<N;i++)sort(sadj[i].rbegin(),sadj[i].rend());
    vector<vector<int>> distances(N,vector<int>(N));
    for(int i=0;i<N;i++){
        priority_queue<pair<int,int>> q;
        q.emplace(0,i);
        vector<int> visited(N,1e18);
        vector<bool> vis(N);
        visited[i] = 0;
        while(!q.empty()){
            auto [dist,idx] = q.top();q.pop();dist=-dist;
            if(vis[idx])continue;
            vis[idx]=true;
            for(auto[v,l,c]:adj[idx])if(!vis[v]){
                int nxttime = 0;
                int currtime = dist%S;
                if(currtime<=c-l)nxttime=dist+l;
                else {
                    nxttime = (dist/S)*S+l+S;
                }
                if(nxttime<visited[v]){
                    visited[v]=nxttime;
                    q.emplace(-nxttime,v);
                }
            }
        }
        distances[i]=visited;
    }
    vector<int> ans(Q);
    vector<vector<tuple<int,int,int>>> queries(N);
    for(int i=0;i<Q;i++)queries[U[i]].emplace_back(T[i],i,V[i]);
    for(int i=0;i<N;i++)sort(queries[i].rbegin(),queries[i].rend());
    vector<vector<int>> distancesviaedge(2*M);
    for(int i=0;i<M;i++){
        // Say we depart from A[i] for x=i and B[i] for x=i+m at C[i]-L[i]
        vector<bool> vis(N);
        vector<int> disti(N,INF);
        priority_queue<pair<int,int>> q;
        q.emplace(-(C[i]-L[i]),A[i]);
        while(!q.empty()){
            auto [dist,idx] = q.top();q.pop();dist=-dist;
            if(vis[idx])continue;
            vis[idx]=true;
            disti[idx] = dist-(C[i]-L[i]);
            for(auto[v,l,c]:adj[idx])if(dist<=c-l and !vis[v])q.emplace(-dist-l,v);
        }
        distancesviaedge[i]=disti;
    }
    for(int i=0;i<M;i++){
        // Say we depart from A[i] for x=i and B[i] for x=i+m at C[i]-L[i]
        vector<bool> vis(N);
        vector<int> disti(N,INF);
        priority_queue<pair<int,int>> q;
        q.emplace(-(C[i]-L[i]),B[i]);
        while(!q.empty()){
            auto [dist,idx] = q.top();q.pop();dist=-dist;
            if(vis[idx])continue;
            vis[idx]=true;
            disti[idx] = dist-(C[i]-L[i]);
            for(auto[v,l,c]:adj[idx])if(dist<=c-l and !vis[v])q.emplace(-dist-l,v);
        }
        distancesviaedge[i+M]=disti;
    }
    for(int i=0;i<N;i++){
        set<pair<int,int>> edges;
        vector<int> dist(N,INF);
        vector<int> addedidx(N);
        auto update_node = [&](int x,int newd){
            if(newd>=dist[x])return;
            if(dist[x]>=INF){
                // First time adding
                edges.insert(make_pair(get<0>(sadj[x][0])-newd,get<3>(sadj[x][0])));
            } else if(addedidx[x]!=sadj[x].size()) {
                edges.erase(make_pair(get<0>(sadj[x][addedidx[x]])-dist[x],get<3>(sadj[x][addedidx[x]])));
                edges.insert(make_pair(get<0>(sadj[x][addedidx[x]])-newd,get<3>(sadj[x][addedidx[x]])));
            }
            dist[x]=newd;
        };
        auto update_edge = [&](int e){
            int v = -1;
            if(e>=M)v=B[e-M];
            else v=A[e];
            edges.erase(make_pair(get<0>(sadj[v][addedidx[v]])-dist[v],get<3>(sadj[v][addedidx[v]])));
            addedidx[v]++;
            if(addedidx[v]!=sadj[v].size())edges.insert(make_pair(get<0>(sadj[v][addedidx[v]])-dist[v],get<3>(sadj[v][addedidx[v]])));
            for(int x=0;x<N;x++)update_node(x,dist[v]+distancesviaedge[e][x]);
        };
        update_node(i,0);
        for(auto[tim,idx,dest]:queries[i]){
            while(!edges.empty() and (--edges.end())->first>=tim)update_edge((--edges.end())->second);
            ans[idx] = dist[dest];
            for(int j=0;j<N;j++){
                if(dist[j]>=INF)continue;
                ans[idx] = min(ans[idx],distances[j][dest]+S-tim);
            }
        }
    }
    return ans;
}

Compilation message

escape_route.cpp: In lambda function:
escape_route.cpp:95:34: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             } else if(addedidx[x]!=sadj[x].size()) {
escape_route.cpp: In lambda function:
escape_route.cpp:107:27: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             if(addedidx[v]!=sadj[v].size())edges.insert(make_pair(get<0>(sadj[v][addedidx[v]])-dist[v],get<3>(sadj[v][addedidx[v]])));

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 65112 KB Output is correct
2 Correct 24 ms 65180 KB Output is correct
3 Correct 81 ms 65008 KB Output is correct
4 Correct 23 ms 65112 KB Output is correct
5 Correct 27 ms 65116 KB Output is correct
6 Correct 21 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 212752 KB Output is correct
2 Correct 867 ms 222016 KB Output is correct
3 Correct 808 ms 211392 KB Output is correct
4 Correct 879 ms 230496 KB Output is correct
5 Correct 824 ms 230356 KB Output is correct
6 Correct 27 ms 65112 KB Output is correct
7 Correct 786 ms 212868 KB Output is correct
8 Correct 651 ms 230248 KB Output is correct
9 Correct 787 ms 212656 KB Output is correct
10 Correct 890 ms 230648 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 65112 KB Output is correct
2 Correct 24 ms 65180 KB Output is correct
3 Correct 81 ms 65008 KB Output is correct
4 Correct 23 ms 65112 KB Output is correct
5 Correct 27 ms 65116 KB Output is correct
6 Correct 21 ms 65116 KB Output is correct
7 Correct 822 ms 212752 KB Output is correct
8 Correct 867 ms 222016 KB Output is correct
9 Correct 808 ms 211392 KB Output is correct
10 Correct 879 ms 230496 KB Output is correct
11 Correct 824 ms 230356 KB Output is correct
12 Correct 27 ms 65112 KB Output is correct
13 Correct 786 ms 212868 KB Output is correct
14 Correct 651 ms 230248 KB Output is correct
15 Correct 787 ms 212656 KB Output is correct
16 Correct 890 ms 230648 KB Output is correct
17 Correct 848 ms 187724 KB Output is correct
18 Correct 798 ms 187472 KB Output is correct
19 Correct 896 ms 200304 KB Output is correct
20 Correct 841 ms 186736 KB Output is correct
21 Correct 874 ms 205524 KB Output is correct
22 Correct 837 ms 205604 KB Output is correct
23 Correct 742 ms 187568 KB Output is correct
24 Correct 605 ms 204172 KB Output is correct
25 Correct 831 ms 188728 KB Output is correct
26 Correct 849 ms 205104 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 65112 KB Output is correct
2 Correct 24 ms 65180 KB Output is correct
3 Correct 81 ms 65008 KB Output is correct
4 Correct 23 ms 65112 KB Output is correct
5 Correct 27 ms 65116 KB Output is correct
6 Correct 21 ms 65116 KB Output is correct
7 Correct 822 ms 212752 KB Output is correct
8 Correct 867 ms 222016 KB Output is correct
9 Correct 808 ms 211392 KB Output is correct
10 Correct 879 ms 230496 KB Output is correct
11 Correct 824 ms 230356 KB Output is correct
12 Correct 27 ms 65112 KB Output is correct
13 Correct 786 ms 212868 KB Output is correct
14 Correct 651 ms 230248 KB Output is correct
15 Correct 787 ms 212656 KB Output is correct
16 Correct 890 ms 230648 KB Output is correct
17 Correct 848 ms 187724 KB Output is correct
18 Correct 798 ms 187472 KB Output is correct
19 Correct 896 ms 200304 KB Output is correct
20 Correct 841 ms 186736 KB Output is correct
21 Correct 874 ms 205524 KB Output is correct
22 Correct 837 ms 205604 KB Output is correct
23 Correct 742 ms 187568 KB Output is correct
24 Correct 605 ms 204172 KB Output is correct
25 Correct 831 ms 188728 KB Output is correct
26 Correct 849 ms 205104 KB Output is correct
27 Correct 1187 ms 189864 KB Output is correct
28 Correct 1350 ms 190772 KB Output is correct
29 Correct 1301 ms 199216 KB Output is correct
30 Correct 1029 ms 188932 KB Output is correct
31 Correct 1388 ms 207032 KB Output is correct
32 Correct 1364 ms 207116 KB Output is correct
33 Correct 667 ms 204600 KB Output is correct
34 Correct 1230 ms 189448 KB Output is correct
35 Correct 1453 ms 207660 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 65112 KB Output is correct
2 Correct 24 ms 65180 KB Output is correct
3 Correct 81 ms 65008 KB Output is correct
4 Correct 23 ms 65112 KB Output is correct
5 Correct 27 ms 65116 KB Output is correct
6 Correct 21 ms 65116 KB Output is correct
7 Correct 822 ms 212752 KB Output is correct
8 Correct 867 ms 222016 KB Output is correct
9 Correct 808 ms 211392 KB Output is correct
10 Correct 879 ms 230496 KB Output is correct
11 Correct 824 ms 230356 KB Output is correct
12 Correct 27 ms 65112 KB Output is correct
13 Correct 786 ms 212868 KB Output is correct
14 Correct 651 ms 230248 KB Output is correct
15 Correct 787 ms 212656 KB Output is correct
16 Correct 890 ms 230648 KB Output is correct
17 Correct 848 ms 187724 KB Output is correct
18 Correct 798 ms 187472 KB Output is correct
19 Correct 896 ms 200304 KB Output is correct
20 Correct 841 ms 186736 KB Output is correct
21 Correct 874 ms 205524 KB Output is correct
22 Correct 837 ms 205604 KB Output is correct
23 Correct 742 ms 187568 KB Output is correct
24 Correct 605 ms 204172 KB Output is correct
25 Correct 831 ms 188728 KB Output is correct
26 Correct 849 ms 205104 KB Output is correct
27 Correct 1187 ms 189864 KB Output is correct
28 Correct 1350 ms 190772 KB Output is correct
29 Correct 1301 ms 199216 KB Output is correct
30 Correct 1029 ms 188932 KB Output is correct
31 Correct 1388 ms 207032 KB Output is correct
32 Correct 1364 ms 207116 KB Output is correct
33 Correct 667 ms 204600 KB Output is correct
34 Correct 1230 ms 189448 KB Output is correct
35 Correct 1453 ms 207660 KB Output is correct
36 Correct 2956 ms 195468 KB Output is correct
37 Correct 3534 ms 196680 KB Output is correct
38 Correct 2695 ms 195868 KB Output is correct
39 Correct 3806 ms 215120 KB Output is correct
40 Correct 3500 ms 213964 KB Output is correct
41 Correct 753 ms 210884 KB Output is correct
42 Correct 3250 ms 196132 KB Output is correct
43 Correct 3300 ms 194028 KB Output is correct