oj.uz

Submission #978572

# Submission time Handle Problem Language Result Execution time Memory
978572 2024-05-09T11:02:36 Z hotboy2703 Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 359604 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[i][j] = 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[k][v]+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 11 ms 65112 KB Output is correct
2 Correct 14 ms 65116 KB Output is correct
3 Correct 37 ms 65116 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 9 ms 65116 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 298056 KB Output is correct
2 Correct 816 ms 297380 KB Output is correct
3 Correct 660 ms 297300 KB Output is correct
4 Correct 815 ms 298176 KB Output is correct
5 Correct 840 ms 297548 KB Output is correct
6 Correct 9 ms 65116 KB Output is correct
7 Correct 642 ms 298056 KB Output is correct
8 Correct 754 ms 297108 KB Output is correct
9 Correct 734 ms 340876 KB Output is correct
10 Correct 825 ms 359604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 65112 KB Output is correct
2 Correct 14 ms 65116 KB Output is correct
3 Correct 37 ms 65116 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 9 ms 65116 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct
7 Correct 762 ms 298056 KB Output is correct
8 Correct 816 ms 297380 KB Output is correct
9 Correct 660 ms 297300 KB Output is correct
10 Correct 815 ms 298176 KB Output is correct
11 Correct 840 ms 297548 KB Output is correct
12 Correct 9 ms 65116 KB Output is correct
13 Correct 642 ms 298056 KB Output is correct
14 Correct 754 ms 297108 KB Output is correct
15 Correct 734 ms 340876 KB Output is correct
16 Correct 825 ms 359604 KB Output is correct
17 Correct 711 ms 278696 KB Output is correct
18 Correct 726 ms 277620 KB Output is correct
19 Correct 798 ms 301560 KB Output is correct
20 Correct 647 ms 281276 KB Output is correct
21 Correct 849 ms 309956 KB Output is correct
22 Correct 944 ms 310484 KB Output is correct
23 Correct 627 ms 280548 KB Output is correct
24 Correct 747 ms 323316 KB Output is correct
25 Correct 711 ms 268340 KB Output is correct
26 Correct 860 ms 309288 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 65112 KB Output is correct
2 Correct 14 ms 65116 KB Output is correct
3 Correct 37 ms 65116 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 9 ms 65116 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct
7 Correct 762 ms 298056 KB Output is correct
8 Correct 816 ms 297380 KB Output is correct
9 Correct 660 ms 297300 KB Output is correct
10 Correct 815 ms 298176 KB Output is correct
11 Correct 840 ms 297548 KB Output is correct
12 Correct 9 ms 65116 KB Output is correct
13 Correct 642 ms 298056 KB Output is correct
14 Correct 754 ms 297108 KB Output is correct
15 Correct 734 ms 340876 KB Output is correct
16 Correct 825 ms 359604 KB Output is correct
17 Correct 711 ms 278696 KB Output is correct
18 Correct 726 ms 277620 KB Output is correct
19 Correct 798 ms 301560 KB Output is correct
20 Correct 647 ms 281276 KB Output is correct
21 Correct 849 ms 309956 KB Output is correct
22 Correct 944 ms 310484 KB Output is correct
23 Correct 627 ms 280548 KB Output is correct
24 Correct 747 ms 323316 KB Output is correct
25 Correct 711 ms 268340 KB Output is correct
26 Correct 860 ms 309288 KB Output is correct
27 Correct 1627 ms 275444 KB Output is correct
28 Correct 1736 ms 273360 KB Output is correct
29 Correct 2005 ms 297996 KB Output is correct
30 Correct 806 ms 277000 KB Output is correct
31 Correct 2061 ms 307220 KB Output is correct
32 Correct 1978 ms 305436 KB Output is correct
33 Correct 797 ms 319548 KB Output is correct
34 Correct 1504 ms 264588 KB Output is correct
35 Correct 1934 ms 307408 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 65112 KB Output is correct
2 Correct 14 ms 65116 KB Output is correct
3 Correct 37 ms 65116 KB Output is correct
4 Correct 9 ms 65116 KB Output is correct
5 Correct 9 ms 65116 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct
7 Correct 762 ms 298056 KB Output is correct
8 Correct 816 ms 297380 KB Output is correct
9 Correct 660 ms 297300 KB Output is correct
10 Correct 815 ms 298176 KB Output is correct
11 Correct 840 ms 297548 KB Output is correct
12 Correct 9 ms 65116 KB Output is correct
13 Correct 642 ms 298056 KB Output is correct
14 Correct 754 ms 297108 KB Output is correct
15 Correct 734 ms 340876 KB Output is correct
16 Correct 825 ms 359604 KB Output is correct
17 Correct 711 ms 278696 KB Output is correct
18 Correct 726 ms 277620 KB Output is correct
19 Correct 798 ms 301560 KB Output is correct
20 Correct 647 ms 281276 KB Output is correct
21 Correct 849 ms 309956 KB Output is correct
22 Correct 944 ms 310484 KB Output is correct
23 Correct 627 ms 280548 KB Output is correct
24 Correct 747 ms 323316 KB Output is correct
25 Correct 711 ms 268340 KB Output is correct
26 Correct 860 ms 309288 KB Output is correct
27 Correct 1627 ms 275444 KB Output is correct
28 Correct 1736 ms 273360 KB Output is correct
29 Correct 2005 ms 297996 KB Output is correct
30 Correct 806 ms 277000 KB Output is correct
31 Correct 2061 ms 307220 KB Output is correct
32 Correct 1978 ms 305436 KB Output is correct
33 Correct 797 ms 319548 KB Output is correct
34 Correct 1504 ms 264588 KB Output is correct
35 Correct 1934 ms 307408 KB Output is correct
36 Correct 7957 ms 274556 KB Output is correct
37 Correct 8883 ms 272692 KB Output is correct
38 Correct 1207 ms 278784 KB Output is correct
39 Execution timed out 9019 ms 243768 KB Time limit exceeded
40 Halted 0 ms 0 KB -