Submission #1211777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211777		tosivanmak	Escape Route (JOI21_escape_route)	C++20	100 / 100	1233 ms	385248 KiB

escape_route

#include<bits/stdc++.h>
#include "escape_route.h"
using namespace std;
#define ll long long
const ll INF=1e18;

ll dist_0[92][92]; priority_queue<pair<ll,ll> >pq; bool vis[92];
struct dat{
    ll graph_id,x,y,l,timing;
    bool operator<(const dat& da)const{
        if(timing!=da.timing)return timing<da.timing;
        return graph_id<da.graph_id;
    }
    bool operator>(const dat& da)const{
        if(timing!=da.timing)return timing>da.timing;
        return graph_id>da.graph_id;
    }
    bool operator==(const dat& da)const{
        if(timing!=da.timing)return 0;
        if(graph_id!=da.graph_id)return 0;
        return 1;
    }
};
struct edge{
    ll v,l,c;
    bool operator<(const edge& edg)const{
        return ((c-l)<(edg.c-edg.l));
    }
};
vector<edge>adj[91];
priority_queue<dat> q;
struct Graph{
    vector<ll>dist[8101];
    vector<ll>points;
    vector<edge>adj[91];
    vector<ll>optimals;
    ll n,gid; ll ass=1;
    void init(ll _n, ll _gid){
        n=_n; gid=_gid;
        vector<ll>d;
        for(int i=0;i<=n;i++)d.push_back(INF);
        d[gid]=0; dist[0]=d; points.push_back(INF);
        optimals=d;
    }
    void add_edge(ll u, ll v, ll l, ll c){
        adj[u].push_back({v,l,c}); adj[v].push_back({u,l,c});
    }
    void compile(){
        for(int i=1;i<=90;i++){
            sort(adj[i].begin(),adj[i].end());
        }
        auto [v,l,c]=adj[gid][adj[gid].size()-1];
        q.push({gid,gid,v,l,c-l});
    }
    ll search(ll x){
        ll l=0,r=points.size()-1;
        while(l<r){
            ll mid=(l+r+1)>>1;
            if(points[mid]>=x)l=mid;
            else r=mid-1;
        }
        return l;
    }
    bool upd(ll x, ll y, ll w){
        adj[x].pop_back();
        if(optimals[x]+w<optimals[y]){
            optimals[y]=optimals[x]+w; return 1;
        }
        return 0;
    }
    ll exhaust_graph(vector<ll>& distances, ll starting_at, ll timer){
        for(int i=1;i<=n;i++){
            if(distances[i]+optimals[starting_at]<optimals[i]){
                optimals[i]=optimals[starting_at]+distances[i];
            }
        }
        dist[ass]=optimals; ass++; points.push_back(min(timer,points[ass-2]));
        return points[points.size()-1];
    }
    void add(){
        ll maxi=-2*INF; edge req; ll from;
        for(int i=1;i<=n;i++){
            if(adj[i].size()==0)continue;
            auto [v,l,c]=adj[i][adj[i].size()-1];
            if(c-l-optimals[i]>maxi){
                from=i;
                maxi=c-l-optimals[i]; req=adj[i][adj[i].size()-1];
            }
        }
        if(maxi!=-2*INF){
            q.push({gid,from,req.v,req.l,maxi});
        }
    }
    // pinpoint c-l-dist

}g[91];

void Dijk(ll x, ll S){
    pq.push({0,x});
    dist_0[x][x]=0;
    while(!pq.empty()){
        ll cur=pq.top().second; pq.pop();
        if(vis[cur])continue;
        vis[cur]=1;
        for(auto& [v,l,c]: adj[cur]){
            ll req=dist_0[x][cur];
            ll rem=req%S;
            if(rem<=c-l){
                if(req+l<dist_0[x][v]){
                    dist_0[x][v]=req+l; pq.push({-dist_0[x][v],v});
                }
            }
            else{
                ll new_dist=dist_0[x][cur]/S+1; new_dist*=S;
                if(new_dist+l<dist_0[x][v]){
                    dist_0[x][v]=new_dist+l; pq.push({-dist_0[x][v],v});
                }
            }
        }
    }
}
vector<ll> calculate_necessary_time(int N, int M, long long S, int Q,
vector<int> A, vector<int> B, vector<ll> L, vector<ll> C, 
vector<int> U, vector<int> V, vector<long long> T) {
    for(int i=0;i<M;i++){
        A[i]++; B[i]++;
        adj[A[i]].push_back({B[i],L[i],C[i]}); adj[B[i]].push_back({A[i],L[i],C[i]});
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            dist_0[i][j]=INF;
        }
    }
    for(int i=1;i<=N;i++){
        Dijk(i,S); for(int j=1;j<=N;j++)vis[j]=0;
    }
    for(int i=0;i<Q;i++)U[i]++,V[i]++;
    for(int i=1;i<=N;i++){
        g[i].init(N,i);
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<M;j++){
            g[i].add_edge(A[j],B[j],L[j],C[j]);
        }
    }
    for(int i=N;i>=1;i--)g[i].compile();
    // dat thing={4,4,2,5,9};
    // dat thing2={3,3,1,2,6};
    // cout<<q.size()<<'\n';
    // while(!q.empty()){
    //     auto [graph_id,x,y,l,timing]=q.top(); q.pop();
    //     cout<<graph_id<<' '<<x<<" "<<y<<" "<<l<<" "<<timing<<endl;
    // }
    while(!q.empty()){
        auto [graph_id,x,y,l,timing]=q.top(); q.pop();
        if(timing<0)break;
        bool success=g[graph_id].upd(x,y,l);
        ll val=-1;
        if(success){
            ll req=g[graph_id].optimals[y];
            ll id=g[y].search(timing+req);
            val=g[graph_id].exhaust_graph(g[y].dist[id],y,timing);
        }
        g[graph_id].add();
        
    }
    // vector<ll>ans; return ans;
    vector<ll>ans;
    for(int i=0;i<Q;i++){
        ll u=U[i],v=V[i],t=T[i];
        ll id=g[u].search(t);
        if(g[u].dist[id][v]!=INF){
            ans.push_back(g[u].dist[id][v]);
        }
        else{
            ll bst=2*INF;
            for(int j=1;j<=N;j++){
                if(g[u].dist[id][j]!=INF){
                    bst=min(bst,dist_0[j][v]+S-t);
                }
            }
            ans.push_back(bst);
        }
    }
    return ans;
}

// int main(){
//     ios::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     ll n,m,s,q;
//     cin>>n>>m>>s>>q;
//     vector<ll>L,C,T;
//     vector<int>A,B,U,V;
//     for(int i=0;i<m;i++){
//         ll a,b,l,c;
//         cin>>a>>b>>l>>c;
//         A.push_back(a);
//         B.push_back(b);
//         L.push_back(l);
//         C.push_back(c);
//     }
//     for(int i=0;i<q;i++){
//         ll u,v,t;
//         cin>>u>>v>>t;
//         U.push_back(u);
//         V.push_back(v);
//         T.push_back(t);
//     }
//     vector<ll>ans=calculate_necessary_time(n,m,s,q,A,B,L,C,U,V,T);
//     for(auto& u: ans)cout<<u<<'\n';
// }

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