Submission #978572

#	Time	Username	Problem	Language	Result	Execution time	Memory
978572		hotboy2703	Escape Route (JOI21_escape_route)	C++17	70 / 100	9019 ms	359604 KiB

escape_route

#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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30