Submission #978447

#	Time	Username	Problem	Language	Result	Execution time	Memory
978447		hotboy2703	Escape Route (JOI21_escape_route)	C++17	5 / 100	9045 ms	190136 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;
    struct query{
        ll u,v,t;
    };
    struct edge{
        ll u,v,l,c;
    };
    vector <edge> all_edge;
    vector <query> all_query;
    vector <ll> ans;
    ll dist1[MAXN+10][MAXN+10];
    pll dist2[MAXN+10][MAXN+10];
    vector <edge> g[MAXN+10];
    ll dist[MAXN+10];
    void solve(){
        for (auto x:all_edge){
            g[x.u].push_back({x.u,x.v,x.l,x.c});
            g[x.v].push_back({x.v,x.u,x.l,x.c});
        }
        for (ll i = 1;i <= n;i ++){
            for (ll j = 1;j <= n;j ++)dist1[i][j] = INF;
            dist1[i][i] = 0;
            priority_queue <pll,vector <pll> ,greater <> > q;
            q.push(MP(dist1[i][i],i));
            while (!q.empty()){
                ll u = q.top().se;
                ll val = q.top().fi;
                q.pop();
                if (val != dist1[i][u])continue;
                for (auto tmp:g[u]){
                    ll v = tmp.v,l = tmp.l,c = tmp.c;
                    if (val + l <= c && val + l < dist1[i][v]){
                        dist1[i][v] = val+l;
                        q.push(MP(dist1[i][v],v));
                    }
                }
            }
//            cout<<"SUS "<<i<<endl;
//            for (ll i = 1;i <= n;i ++){
//                for (ll j = 1;j <= n;j ++)cout<<dist1[i][j]<<' ';
//                cout<<'\n';
//            }
        }
//        for (ll i = 1;i <= n;i ++){
//            for (ll j = 1;j <= n;j ++)cout<<dist1[i][j]<<' ';
//            cout<<'\n';
//        }
        for (ll i = 1;i <= n;i ++){
            for (ll j = 1;j <= n;j ++)dist2[i][j] = MP(INF,INF);
            dist2[i][i] = MP(1,0);
        }
        for (ll i = 1;i <= n;i ++){
            for (ll j = 1;j <= n;j ++)dist2[i][j] = min(dist2[i][j],dist1[i][j]==INF?MP(INF,INF):MP(1LL,dist1[i][j]));
        }
        for (ll k = 1;k <= n;k ++){
            for (ll i = 1;i <= n;i ++){
                for (ll j = 1;j <= n;j ++){
                    dist2[i][j] = min(dist2[i][j],MP(dist2[i][k].fi + dist2[k][j].fi,dist2[k][j].se));
                }
            }
        }
        for (auto x:all_query){
            ll u,v,t;
            tie(u,v,t) = tie(x.u,x.v,x.t);
            for (ll j = 1;j <= n;j ++)dist[j] = INF;

            dist[u] = t;
            priority_queue <pll,vector <pll> ,greater <> > q;
            q.push(MP(dist[u],u));
            pll res = MP(INF,INF);
            while (!q.empty()){
                ll u = q.top().se;
                ll val = q.top().fi;
                q.pop();
                if (val != dist[u])continue;
                if (u != v)res = min(res,dist2[u][v]);
                if (u == v)res = min(res,MP(0LL,val));
                for (auto tmp:g[u]){
                    ll v = tmp.v,l = tmp.l,c = tmp.c;
//                    if (u==3&&v==4)cout<<u<<' '<<v<<' '<<val<<' '<<l<<' '<<c<<endl;
                    if (val + l <= c && val + l < dist[v]){
                        dist[v] = val+l;
                        q.push(MP(dist[v],v));
                    }
                }
            }
//            cout<<res.fi<<' '<<res.se<<'\n';
            ans.push_back(res.fi * s + res.se - 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 = 0;i < m;i ++){
        ll u,v,l,c;
        u = A[i]+1,v = B[i]+1,l = L[i],c = C[i];
        all_edge.push_back({u,v,l,c});
    }
    for (ll i = 0;i < q;i ++){
        all_query.push_back({U[i]+1,V[i]+1,T[i]});
    }
    solve();

    return ans;
}

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