Submission #978938

#	Time	Username	Problem	Language	Result	Execution time	Memory
978938		hotboy2703	Escape Route (JOI21_escape_route)	C++17	100 / 100	1565 ms	331732 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 st[MAXN+10][MAXN+10][MAXN+10],en[MAXN+10][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;
                    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];
        }
        for (ll i = 1;i <= n;i ++){
            for (ll k = 1;k <= n;k ++){
                for (ll j = 1;j <= n;j ++){dist[j] = INF;used[j] = 0;}
                dist[i] = c[i][k];
                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 (dist[u] + l[u][v] <= min(c[u][v],dist[v]))dist[v] = dist[u] + l[u][v];
                    }
                }
                for (ll j = 1;j <= n;j ++)en[i][k][j] = dist[j];
            }
        }
        for (ll i = 1;i <= n;i ++){
            for (ll k = 1;k <= n;k ++){
                for (ll j = 1;j <= n;j ++){dist[j] = -INF;used[j] = 0;}
                dist[i] = c[i][k];
                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 (min(dist[u],c[u][v]) - l[u][v] >= max(0LL,dist[v]))dist[v] = min(dist[u],c[u][v]) - l[u][v];
                    }
                }
                for (ll j = 1;j <= n;j ++)st[i][k][j] = dist[j];
            }
        }
        sort(all_query.begin(),all_query.end(),[&](query x,query y){
                if (x.u != y.u)return x.u<y.u;
                else return x.t > y.t;

             });
        for (ll i = 1,ptr1 = 0;i <= n;i ++){

            vector <pair <ll,pll > > pos;
            for (ll j = 1;j <= n;j ++){
                for (ll k = 1;k <= n;k ++){
                    if (st[j][k][i] >= 0){
                        pos.push_back(MP(st[j][k][i],MP(j,k)));
                    }
                }
            }
            sort(pos.begin(),pos.end(),[&](pair <ll,pll > x, pair <ll,pll > y){return x.fi > y.fi;});
            for (ll j = 1;j <= n;j ++){
                dist[j] = INF;
            }
            dist[i]=0;
            ll ptr2 = 0;
            for (;ptr1 < sz(all_query) && all_query[ptr1].u==i;ptr1++){
//                cout<<ptr1<<endl;
                for (;ptr2 < sz(pos) && pos[ptr2].fi >= all_query[ptr1].t;ptr2++){
                    for (ll j = 1;j <= n;j ++){
                        if (en[pos[ptr2].se.fi][pos[ptr2].se.se][j] != INF){
                            dist[j] = min(dist[j],en[pos[ptr2].se.fi][pos[ptr2].se.se][j]-st[pos[ptr2].se.fi][pos[ptr2].se.se][i]);
                        }
                    }
                }
                if (dist[all_query[ptr1].v]!=INF)ans[all_query[ptr1].id] = dist[all_query[ptr1].v];
                else {
                    ans[all_query[ptr1].id] = INF;
                    for (ll j = 1;j <= n;j ++){
                        if (dist[j] != INF)ans[all_query[ptr1].id] = min(ans[all_query[ptr1].id],pre[j][all_query[ptr1].v]+s-all_query[ptr1].t);
                    }
                }
            }
        }

    }
}
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;
}

Compilation message (stderr)

escape_route.cpp:22:8: warning: '{anonymous}::last_c' defined but not used [-Wunused-variable]
   22 |     ll last_c[MAXN+10];
      |        ^~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 30 / 30