Submission #908802

#	Time	Username	Problem	Language	Result	Execution time	Memory
908802		alexander707070	Escape Route (JOI21_escape_route)	C++17	35 / 100	9097 ms	224776 KiB

escape_route

#include<bits/stdc++.h>
#include "escape_route.h"

#define MAXN 107
using namespace std;
 
const long long inf=1e17;
 
struct edge{
    int to;
    long long l,c;
};
 
int n,m,qs,minv,from,to;
long long s,w,ans,mins;
vector<long long> sol;
int a[10007],b[10007];
long long l[10007],c[10007];
long long dist[MAXN][MAXN],dst[MAXN];
long long cost[MAXN][MAXN],lim[MAXN][MAXN];
int parent[MAXN];
vector<edge> v[MAXN];

int li[MAXN],tim;
 
queue<int> qq;
priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater< pair<long long,int> > > q;
 
void dijkstra(int x){
    for(int i=1;i<=n;i++){
        dist[x][i]=inf;
    }
    dist[x][x]=0; tim++;
    q.push({0,x});
 
    while(!q.empty()){
        minv=q.top().second;
        q.pop();
 
        if(li[minv]==tim)continue;
        li[minv]=tim;
 
        for(int i=0;i<v[minv].size();i++){
            if(li[v[minv][i].to]==tim or dist[x][v[minv][i].to]<=dist[x][minv]+v[minv][i].l or dist[x][minv]>v[minv][i].c-v[minv][i].l)continue;
            dist[x][v[minv][i].to]=dist[x][minv]+v[minv][i].l;
            q.push({dist[x][v[minv][i].to],v[minv][i].to});
        }
    }
}
 
void query(int x,long long t){
    for(int i=1;i<=n;i++){
        dst[i]=inf;
        parent[i]=-1;
    }

    dst[x]=t; tim++;
    qq.push(x);
 
    while(!qq.empty()){
        minv=qq.front();
        qq.pop();
 
        for(int i=0;i<v[minv].size();i++){
            if(dst[v[minv][i].to]<=dst[minv]+v[minv][i].l or dst[minv]>v[minv][i].c-v[minv][i].l)continue;
            dst[v[minv][i].to]=dst[minv]+v[minv][i].l;

            parent[v[minv][i].to]=minv;
            qq.push(v[minv][i].to);
        }
    }
}

vector< pair<long long,vector<int> > > dists[MAXN];

void findchanges(int x,long long l,long long r,vector<int> ls,vector<int> rs){
    if(l+1==r){
        dists[x].push_back({l,ls});
        return;
    }

    long long mid=(l+r)/2;

    query(x,mid);
    vector<int> curr={};
    for(int i=1;i<=n;i++){
        curr.push_back(parent[i]);
    }

    if(ls!=curr){
        findchanges(x,l,mid,ls,curr);
    }
    if(curr!=rs){
        findchanges(x,mid,r,curr,rs);
    }
}
 
bool u[MAXN][MAXN][MAXN];
long long dp[MAXN][MAXN][MAXN];
 
long long ff(int x,int y,int day){
    if(x==y)return 0;
    if(day>n)return inf;
 
    if(u[x][y][day])return dp[x][y][day];
    u[x][y][day]=true;
    dp[x][y][day]=inf;
 
    for(int p=1;p<=n;p++){
        if(dist[x][p]!=inf){
            if(p!=y){
                dp[x][y][day]=min(dp[x][y][day],ff(p,y,day+1)+s);
            }else{
                dp[x][y][day]=min(dp[x][y][day],ff(p,y,day+1)+dist[x][y]);
            }
        }
    }
 
    return dp[x][y][day];
}

long long path(int x){
    if(parent[x]==-1 or li[x]==tim)return dst[x];
    li[x]=tim;

    dst[x]=path(parent[x])+cost[parent[x]][x];

    return dst[x];
}
 
vector<long long> calculate_necessary_time(int N, int M, long long S, int Q, vector<int> A, vector<int> B, vector<long long> L, vector<long long> C, vector<int> U,vector<int> V, vector<long long> T){
    n=N; m=M; s=S; qs=Q;
    //cin>>n>>m>>s>>qs;
    
    for(int i=1;i<=m;i++){
        a[i]=A[i-1]; b[i]=B[i-1]; l[i]=L[i-1]; c[i]=C[i-1];
        //cin>>a[i]>>b[i]>>l[i]>>c[i];
        a[i]++; b[i]++;
        v[a[i]].push_back({b[i],l[i],c[i]});
        v[b[i]].push_back({a[i],l[i],c[i]});

        cost[a[i]][b[i]]=l[i];
        cost[b[i]][a[i]]=l[i];

        lim[a[i]][b[i]]=c[i];
        lim[b[i]][a[i]]=c[i];
    }
 
    for(int i=1;i<=n;i++){
        dijkstra(i);
    }

    for(int i=1;i<=n;i++){

        w=0;
        while(true){

            query(i,w); mins=inf;
            vector<int> curr;

            for(int f=1;f<=n;f++){
                if(parent[f]!=-1){
                    mins=min(mins,lim[parent[f]][f]-cost[parent[f]][f]-dst[parent[f]]);
                }
                curr.push_back(parent[f]);
            }

            dists[i].push_back({w+mins,curr});
            if(mins==inf)break;
            w+=mins+1;
        }
    }
 
    for(int i=1;i<=qs;i++){
        
        from=U[i-1]; to=V[i-1]; w=T[i-1];
        //cin>>from>>to>>w;
        from++; to++;

        int lt=-1,rt=dists[from].size(),mid;
        while(lt+1<rt){
            mid=(lt+rt)/2;
            if(w<=dists[from][mid].first){
                rt=mid;
            }else{
                lt=mid;
            }
        }
        lt=rt;

        for(int f=1;f<=n;f++){
            dst[f]=inf;
            parent[f]=dists[from][lt].second[f-1];
        }
        dst[from]=w;


        tim++; ans=inf;

        for(int f=1;f<=n;f++){
            if(path(f)!=inf){

                if(f!=to)ans=min(ans,s+ff(f,to,0));
                else ans=min(ans,path(f));
            }
        }
 
        sol.push_back(ans-w);
    }

    return sol;
}

/*
int main(){
    calculate_necessary_time();
}
*/

Compilation message (stderr)

escape_route.cpp: In function 'void dijkstra(int)':
escape_route.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int i=0;i<v[minv].size();i++){
      |                     ~^~~~~~~~~~~~~~~
escape_route.cpp: In function 'void query(int, long long int)':
escape_route.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int i=0;i<v[minv].size();i++){
      |                     ~^~~~~~~~~~~~~~~

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