oj.uz

Submission #978680

# Submission time Handle Problem Language Result Execution time Memory
978680 2024-05-09T13:28:16 Z hotboy2703 Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 352900 KB 
#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
namespace{
    const ll MAXN = 90;
    const ll INF = 1e18;
    ll n,m,s,q;
    ll c[MAXN+10][MAXN+10],l[MAXN+10][MAXN+10];
    ll pre[MAXN+10][MAXN+10];
    bool used[MAXN+10];
    ll dist[MAXN+10];
    ll last_c[MAXN+10];
    struct query{
        ll u,v,t,id;
    };
    vector <query> all_query;
    vector <ll> ans;
    void solve(){
        ans.resize(sz(all_query));
        sort(all_query.begin(),all_query.end(),[&](query x,query y){return x.u < y.u;});
        for (ll i = 1;i <= n;i ++){
            for (ll j = 1;j <= n;j ++){dist[j] = INF;used[j] = 0;}
            dist[i] = 0;
 
            for (ll z = 1;z <= n;z ++){
                ll u = 0;
                for (ll j = 1;j <= n;j ++){
                    if (!used[j] && (!u || dist[j] < dist[u]))u=j;
                }
                used[u] = 1;
                for (ll v = 1;v <= n;v ++){
                    if (used[v])continue;
                    if (c[u][v] == 0)continue;
//                    if (i == 1 && u == 3)cout<<v<<endl;
                    ll x = dist[u]%s;
                    ll w;
                    if (x + l[u][v] > c[u][v])w = dist[u]+s-x+l[u][v];
                    else w = dist[u]+l[u][v];
                    dist[v] = min(dist[v],w);
                }
            }
            for (ll j = 1;j <= n;j ++)pre[j][i] = dist[j];
        }
//        cout<<l[3][4]<<' '<<c[3][4]<<endl;
//        for (ll i = 1;i <= n;i ++)for (ll j = 1;j <= n;j ++)cout<<pre[i][j]<<" \n"[j==n];
        for (ll i = 1,ptr = 0;i <= n;i ++){
            vector <query> cur_query;
            while (ptr<sz(all_query)&&all_query[ptr].u==i){
                cur_query.push_back(all_query[ptr]);
                ptr++;
            }
            sort(cur_query.begin(),cur_query.end(),[&](query x,query y){return x.t < y.t;});
//            for (auto x:cur_query){
//                cout<<x.u<<' '<<x.v<<' '<<x.t<<endl;
//            }
            ll ptr_cur=0;
            ll st = 0;
            while (1){
//                cout<<st<<endl;
                for (ll j = 1;j <= n;j ++){
                    dist[j] = INF;
                    used[j] = 0;
                }
                dist[i] = st;
                ll range = INF;
                for (ll j = 1;j <= n;j ++){
                    ll u = 0;
                    for (ll k = 1;k <= n;k ++){
                        if (!used[k]&&(!u || dist[k]<dist[u]))u=k;
                    }
                    used[u] = 1;
                    if (dist[u]==INF)break;
                    if (u != i)range = min(range,last_c[u] - dist[u]);
                    for (ll v = 1;v <= n;v ++){
                        if (!used[v] && c[u][v]){
                            if (dist[u] + l[u][v] <= min(dist[v],c[u][v])){
                                last_c[v] = c[u][v];
                                dist[v] = dist[u] + l[u][v];
                            }
                        }
                    }
                }
                while (ptr_cur<sz(cur_query)&&cur_query[ptr_cur].t <= st+range){
                    ll u,v,t,id,res=INF;
                    query x = cur_query[ptr_cur];
                    tie(u,v,t,id) = tie(x.u,x.v,x.t,x.id);
                    if (dist[v]!=INF)res = dist[v]-st;
                    else{
                        for (ll k = 1;k <= n;k ++){
                            if (dist[k] != INF){
                                res = min(res,pre[v][k]+s-t);
                            }
                        }
                    }
                    ans[id]=res;
                    ptr_cur++;
                }
                if (range==INF)break;
//                cout<<range<<endl;
                st+=range+1;
 
            }
        }
 
    }
}
std::vector<long long> calculate_necessary_time(
    int N, int M, long long S, 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) {
    n = N,m = M,s = S,q = Q;
    for (ll i = 1;i <= n;i ++){
        for (ll j = 1;j <= n;j ++){
            c[i][j] = 0;
            l[i][j] = 1;
        }
    }
    for (ll i = 0;i < m;i ++){
        ll u,v;
        u = A[i]+1,v = B[i]+1;
        c[u][v] = c[v][u] = C[i];
        l[u][v] = l[v][u] = L[i];
    }
    for (ll i = 0;i < q;i ++){
        all_query.push_back({U[i]+1,V[i]+1,T[i],i});
    }
    solve();
 
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65196 KB Output is correct
2 Correct 15 ms 65448 KB Output is correct
3 Correct 37 ms 65124 KB Output is correct
4 Correct 10 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 903 ms 330452 KB Output is correct
2 Correct 879 ms 343324 KB Output is correct
3 Correct 692 ms 335360 KB Output is correct
4 Correct 881 ms 352900 KB Output is correct
5 Correct 868 ms 350988 KB Output is correct
6 Correct 9 ms 65112 KB Output is correct
7 Correct 678 ms 335724 KB Output is correct
8 Correct 827 ms 350076 KB Output is correct
9 Correct 758 ms 337484 KB Output is correct
10 Correct 868 ms 350344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65196 KB Output is correct
2 Correct 15 ms 65448 KB Output is correct
3 Correct 37 ms 65124 KB Output is correct
4 Correct 10 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 903 ms 330452 KB Output is correct
8 Correct 879 ms 343324 KB Output is correct
9 Correct 692 ms 335360 KB Output is correct
10 Correct 881 ms 352900 KB Output is correct
11 Correct 868 ms 350988 KB Output is correct
12 Correct 9 ms 65112 KB Output is correct
13 Correct 678 ms 335724 KB Output is correct
14 Correct 827 ms 350076 KB Output is correct
15 Correct 758 ms 337484 KB Output is correct
16 Correct 868 ms 350344 KB Output is correct
17 Correct 726 ms 270376 KB Output is correct
18 Correct 748 ms 271884 KB Output is correct
19 Correct 795 ms 296100 KB Output is correct
20 Correct 643 ms 276756 KB Output is correct
21 Correct 823 ms 303344 KB Output is correct
22 Correct 844 ms 304132 KB Output is correct
23 Correct 626 ms 275240 KB Output is correct
24 Correct 774 ms 314872 KB Output is correct
25 Correct 705 ms 263136 KB Output is correct
26 Correct 875 ms 303128 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65196 KB Output is correct
2 Correct 15 ms 65448 KB Output is correct
3 Correct 37 ms 65124 KB Output is correct
4 Correct 10 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 903 ms 330452 KB Output is correct
8 Correct 879 ms 343324 KB Output is correct
9 Correct 692 ms 335360 KB Output is correct
10 Correct 881 ms 352900 KB Output is correct
11 Correct 868 ms 350988 KB Output is correct
12 Correct 9 ms 65112 KB Output is correct
13 Correct 678 ms 335724 KB Output is correct
14 Correct 827 ms 350076 KB Output is correct
15 Correct 758 ms 337484 KB Output is correct
16 Correct 868 ms 350344 KB Output is correct
17 Correct 726 ms 270376 KB Output is correct
18 Correct 748 ms 271884 KB Output is correct
19 Correct 795 ms 296100 KB Output is correct
20 Correct 643 ms 276756 KB Output is correct
21 Correct 823 ms 303344 KB Output is correct
22 Correct 844 ms 304132 KB Output is correct
23 Correct 626 ms 275240 KB Output is correct
24 Correct 774 ms 314872 KB Output is correct
25 Correct 705 ms 263136 KB Output is correct
26 Correct 875 ms 303128 KB Output is correct
27 Correct 1640 ms 268072 KB Output is correct
28 Correct 1756 ms 268332 KB Output is correct
29 Correct 2013 ms 294312 KB Output is correct
30 Correct 754 ms 271496 KB Output is correct
31 Correct 2016 ms 298588 KB Output is correct
32 Correct 2012 ms 298304 KB Output is correct
33 Correct 841 ms 311944 KB Output is correct
34 Correct 1528 ms 258812 KB Output is correct
35 Correct 1979 ms 299060 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65196 KB Output is correct
2 Correct 15 ms 65448 KB Output is correct
3 Correct 37 ms 65124 KB Output is correct
4 Correct 10 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 903 ms 330452 KB Output is correct
8 Correct 879 ms 343324 KB Output is correct
9 Correct 692 ms 335360 KB Output is correct
10 Correct 881 ms 352900 KB Output is correct
11 Correct 868 ms 350988 KB Output is correct
12 Correct 9 ms 65112 KB Output is correct
13 Correct 678 ms 335724 KB Output is correct
14 Correct 827 ms 350076 KB Output is correct
15 Correct 758 ms 337484 KB Output is correct
16 Correct 868 ms 350344 KB Output is correct
17 Correct 726 ms 270376 KB Output is correct
18 Correct 748 ms 271884 KB Output is correct
19 Correct 795 ms 296100 KB Output is correct
20 Correct 643 ms 276756 KB Output is correct
21 Correct 823 ms 303344 KB Output is correct
22 Correct 844 ms 304132 KB Output is correct
23 Correct 626 ms 275240 KB Output is correct
24 Correct 774 ms 314872 KB Output is correct
25 Correct 705 ms 263136 KB Output is correct
26 Correct 875 ms 303128 KB Output is correct
27 Correct 1640 ms 268072 KB Output is correct
28 Correct 1756 ms 268332 KB Output is correct
29 Correct 2013 ms 294312 KB Output is correct
30 Correct 754 ms 271496 KB Output is correct
31 Correct 2016 ms 298588 KB Output is correct
32 Correct 2012 ms 298304 KB Output is correct
33 Correct 841 ms 311944 KB Output is correct
34 Correct 1528 ms 258812 KB Output is correct
35 Correct 1979 ms 299060 KB Output is correct
36 Correct 8166 ms 268484 KB Output is correct
37 Execution timed out 9041 ms 221496 KB Time limit exceeded
38 Halted 0 ms 0 KB -