oj.uz

Submission #415831

# Submission time Handle Problem Language Result Execution time Memory
415831 2021-06-01T15:23:10 Z koioi.org-koosaga Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 1168012 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;

struct edg{
    int pos;
    lint L, C;
};

struct node{
    int i, j; lint max_time;
    bool operator<(const node &n)const{
        return max_time < n.max_time;
    }
};

lint daybreak[96][96];
lint dayfinish[96][96];
lint adj[96][96], dp[96][96];
vector<edg> gph[96];

vector<pi> prec[96][96];
lint S;

void Do(int n){
    for(int u = 0; u < n; u++){
        for(auto &e : gph[u]){
            int v = e.pos;
            vector<lint> dist1(n, -3e18), dist2(n, 3e18);
            // backward shortest path
            {
                dist1[u] = e.C - e.L;
                vector<int> vis(n);
                for(int it = 0; it < n; it++){
                    pi ret(-5e18, 5e18);
                    for(int i = 0; i < n; i++){
                        if(!vis[i]) ret = max(ret, pi(dist1[i], i));
                    }
                    int x = ret.second;
                    vis[x] = 1;
                    for(auto &e : gph[x]){
                        if(dist1[e.pos] < dist1[x] - e.L && dist1[x] < e.C){
                            dist1[e.pos] = dist1[x] - e.L;
                        }
                    }
                }
            }
            // forward shortest path
            {
                dist2[v] = e.C;
                vector<int> vis(n);
                for(int it = 0; it < n; it++){
                    pi ret(5e18, 5e18);
                    for(int i = 0; i < n; i++){
                        if(!vis[i]) ret = min(ret, pi(dist2[i], i));
                    }
                    int x = ret.second;
                    vis[x] = 1;
                    for(auto &e : gph[x]){
                        if(dist2[e.pos] > dist2[x] + e.L && dist2[x] + e.L <= e.C){
                            dist2[e.pos] = dist2[x] + e.L;
                        }
                    }
                }
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(dist2[j] <= S && dist1[i] >= 0){
                        prec[i][j].emplace_back(dist1[i], dist2[j] - dist1[i]);
                    }
                }
            }
        }
    }
}

// wtf just use namespace std and pairs
std::vector<long long> calculate_necessary_time(
        int N, int M, long long Sfuck, int Q, std::vector<int> A, std::vector<int> B,
        std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
        std::vector<int> V, std::vector<long long> T) {
    S = Sfuck;
    for(int i = 0; i < M; i++){
        gph[A[i]].push_back({B[i], L[i], C[i]});
        gph[B[i]].push_back({A[i], L[i], C[i]});
    }
    {
        priority_queue<node> pq;
        memset(daybreak, 0x3f, sizeof(daybreak));
        auto enq = [&](int s, int e, lint x){
            if(daybreak[s][e] > x){
                daybreak[s][e] = x;
                pq.push({s, e, -x});
            }
        };
        for(int i = 0; i < N; i++){
            enq(i, i, 0);
        }
        while(sz(pq)){
            auto x = pq.top(); pq.pop();
            x.max_time = -x.max_time;
            if(daybreak[x.i][x.j] != x.max_time) continue;
            for(auto &e : gph[x.j]){
                if(x.max_time + e.L <= e.C){
                    enq(x.i, e.pos, x.max_time + e.L);
                }
            }
        }
    }
    {
        priority_queue<node> pq;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                dayfinish[i][j] = -1e18;
            }
        }
        auto enq = [&](int s, int e, lint x){
            if(dayfinish[s][e] < x){
                dayfinish[s][e] = x;
                pq.push({s, e, x});
            }
        };
        for(int i = 0; i < N; i++){
            enq(i, i, S);
        }
        while(sz(pq)){
            auto x = pq.top(); pq.pop();
            if(dayfinish[x.i][x.j] != x.max_time) continue;
            for(auto &e : gph[x.i]){
                lint val = min(x.max_time, e.C) - e.L;
                if(val >= 0) enq(e.pos, x.j, val);
            }
        }
    }
    {
        memset(adj, 0x3f, sizeof(adj));
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(dayfinish[i][j] >= 0) adj[i][j] = 1;
                if(i == j) adj[i][j] = 0;
            }
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                for(int k = 0; k < N; k++){
                    adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]);
                }
            }
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                assert(adj[i][j] <= N);
                dp[i][j] = 1e18;
                for(int k = 0; k < N; k++){
                    dp[i][j] = min(adj[i][k] * S + daybreak[k][j], dp[i][j]);
                }
            }
        }
    }
    Do(N);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            auto aux = prec[i][j];
            sort(all(aux), [&](const pi &a, const pi &b){
                return pi(a.first, -a.second) < pi(b.first, -b.second);
            });
            reverse(all(aux));
            prec[i][j].clear();
            for(auto &x : aux){
                if(sz(prec[i][j]) && prec[i][j].back().second <= x.second) continue;
                prec[i][j].push_back(x);
            }
            reverse(all(prec[i][j]));
        }
    }
    vector<lint> ans(Q);
    for(int i = 0; i < Q; i++){
        if(dayfinish[U[i]][V[i]] >= T[i]){
            auto it = upper_bound(all(prec[U[i]][V[i]]), pi(T[i], -1));
            ans[i] = it->second;
            continue;
        }
        lint ret = 1e18;
        for(int j = 0; j < N; j++){
            if(dayfinish[U[i]][j] >= T[i]){
                ret = min(ret, S - T[i] + dp[j][V[i]]);
            }
        }
        ans[i] = ret;
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65324 KB Output is correct
2 Correct 38 ms 65160 KB Output is correct
3 Correct 307 ms 65264 KB Output is correct
4 Correct 34 ms 65220 KB Output is correct
5 Correct 50 ms 65232 KB Output is correct
6 Correct 31 ms 65280 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 156808 KB Output is correct
2 Correct 698 ms 170024 KB Output is correct
3 Correct 631 ms 156960 KB Output is correct
4 Correct 803 ms 170972 KB Output is correct
5 Correct 859 ms 170968 KB Output is correct
6 Correct 32 ms 65160 KB Output is correct
7 Correct 667 ms 159480 KB Output is correct
8 Correct 515 ms 134504 KB Output is correct
9 Correct 685 ms 147964 KB Output is correct
10 Correct 840 ms 170088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65324 KB Output is correct
2 Correct 38 ms 65160 KB Output is correct
3 Correct 307 ms 65264 KB Output is correct
4 Correct 34 ms 65220 KB Output is correct
5 Correct 50 ms 65232 KB Output is correct
6 Correct 31 ms 65280 KB Output is correct
7 Correct 799 ms 156808 KB Output is correct
8 Correct 698 ms 170024 KB Output is correct
9 Correct 631 ms 156960 KB Output is correct
10 Correct 803 ms 170972 KB Output is correct
11 Correct 859 ms 170968 KB Output is correct
12 Correct 32 ms 65160 KB Output is correct
13 Correct 667 ms 159480 KB Output is correct
14 Correct 515 ms 134504 KB Output is correct
15 Correct 685 ms 147964 KB Output is correct
16 Correct 840 ms 170088 KB Output is correct
17 Correct 936 ms 156808 KB Output is correct
18 Correct 1008 ms 156208 KB Output is correct
19 Correct 846 ms 171100 KB Output is correct
20 Correct 727 ms 158536 KB Output is correct
21 Correct 1084 ms 171476 KB Output is correct
22 Correct 1043 ms 171072 KB Output is correct
23 Correct 703 ms 158748 KB Output is correct
24 Correct 563 ms 134408 KB Output is correct
25 Correct 871 ms 146752 KB Output is correct
26 Correct 1089 ms 170936 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65324 KB Output is correct
2 Correct 38 ms 65160 KB Output is correct
3 Correct 307 ms 65264 KB Output is correct
4 Correct 34 ms 65220 KB Output is correct
5 Correct 50 ms 65232 KB Output is correct
6 Correct 31 ms 65280 KB Output is correct
7 Correct 799 ms 156808 KB Output is correct
8 Correct 698 ms 170024 KB Output is correct
9 Correct 631 ms 156960 KB Output is correct
10 Correct 803 ms 170972 KB Output is correct
11 Correct 859 ms 170968 KB Output is correct
12 Correct 32 ms 65160 KB Output is correct
13 Correct 667 ms 159480 KB Output is correct
14 Correct 515 ms 134504 KB Output is correct
15 Correct 685 ms 147964 KB Output is correct
16 Correct 840 ms 170088 KB Output is correct
17 Correct 936 ms 156808 KB Output is correct
18 Correct 1008 ms 156208 KB Output is correct
19 Correct 846 ms 171100 KB Output is correct
20 Correct 727 ms 158536 KB Output is correct
21 Correct 1084 ms 171476 KB Output is correct
22 Correct 1043 ms 171072 KB Output is correct
23 Correct 703 ms 158748 KB Output is correct
24 Correct 563 ms 134408 KB Output is correct
25 Correct 871 ms 146752 KB Output is correct
26 Correct 1089 ms 170936 KB Output is correct
27 Correct 2823 ms 336336 KB Output is correct
28 Correct 2781 ms 333952 KB Output is correct
29 Correct 2241 ms 399844 KB Output is correct
30 Correct 1862 ms 373480 KB Output is correct
31 Correct 2946 ms 408564 KB Output is correct
32 Correct 2698 ms 408772 KB Output is correct
33 Correct 673 ms 197448 KB Output is correct
34 Correct 2421 ms 364160 KB Output is correct
35 Correct 2787 ms 399748 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65324 KB Output is correct
2 Correct 38 ms 65160 KB Output is correct
3 Correct 307 ms 65264 KB Output is correct
4 Correct 34 ms 65220 KB Output is correct
5 Correct 50 ms 65232 KB Output is correct
6 Correct 31 ms 65280 KB Output is correct
7 Correct 799 ms 156808 KB Output is correct
8 Correct 698 ms 170024 KB Output is correct
9 Correct 631 ms 156960 KB Output is correct
10 Correct 803 ms 170972 KB Output is correct
11 Correct 859 ms 170968 KB Output is correct
12 Correct 32 ms 65160 KB Output is correct
13 Correct 667 ms 159480 KB Output is correct
14 Correct 515 ms 134504 KB Output is correct
15 Correct 685 ms 147964 KB Output is correct
16 Correct 840 ms 170088 KB Output is correct
17 Correct 936 ms 156808 KB Output is correct
18 Correct 1008 ms 156208 KB Output is correct
19 Correct 846 ms 171100 KB Output is correct
20 Correct 727 ms 158536 KB Output is correct
21 Correct 1084 ms 171476 KB Output is correct
22 Correct 1043 ms 171072 KB Output is correct
23 Correct 703 ms 158748 KB Output is correct
24 Correct 563 ms 134408 KB Output is correct
25 Correct 871 ms 146752 KB Output is correct
26 Correct 1089 ms 170936 KB Output is correct
27 Correct 2823 ms 336336 KB Output is correct
28 Correct 2781 ms 333952 KB Output is correct
29 Correct 2241 ms 399844 KB Output is correct
30 Correct 1862 ms 373480 KB Output is correct
31 Correct 2946 ms 408564 KB Output is correct
32 Correct 2698 ms 408772 KB Output is correct
33 Correct 673 ms 197448 KB Output is correct
34 Correct 2421 ms 364160 KB Output is correct
35 Correct 2787 ms 399748 KB Output is correct
36 Execution timed out 9173 ms 1168012 KB Time limit exceeded
37 Halted 0 ms 0 KB -