oj.uz

Submission #908803

# Submission time Handle Problem Language Result Execution time Memory
908803 2024-01-16T22:11:08 Z alexander707070 Escape Route (JOI21_escape_route) C++17
35 / 100
 9000 ms 232576 KB 
#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;
bool inq[MAXN];

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();
        inq[minv]=false;
        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;

            if(!inq[v[minv][i].to]){
                inq[v[minv][i].to]=true;
                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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65112 KB Output is correct
2 Correct 24 ms 65372 KB Output is correct
3 Correct 57 ms 65116 KB Output is correct
4 Correct 13 ms 65116 KB Output is correct
5 Correct 21 ms 65208 KB Output is correct
6 Correct 15 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2166 ms 182996 KB Output is correct
2 Correct 1878 ms 207876 KB Output is correct
3 Correct 1136 ms 183792 KB Output is correct
4 Correct 2425 ms 217884 KB Output is correct
5 Correct 2420 ms 216660 KB Output is correct
6 Correct 12 ms 65112 KB Output is correct
7 Correct 1273 ms 182940 KB Output is correct
8 Correct 632 ms 223668 KB Output is correct
9 Correct 1754 ms 175488 KB Output is correct
10 Correct 2480 ms 216680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65112 KB Output is correct
2 Correct 24 ms 65372 KB Output is correct
3 Correct 57 ms 65116 KB Output is correct
4 Correct 13 ms 65116 KB Output is correct
5 Correct 21 ms 65208 KB Output is correct
6 Correct 15 ms 65116 KB Output is correct
7 Correct 2166 ms 182996 KB Output is correct
8 Correct 1878 ms 207876 KB Output is correct
9 Correct 1136 ms 183792 KB Output is correct
10 Correct 2425 ms 217884 KB Output is correct
11 Correct 2420 ms 216660 KB Output is correct
12 Correct 12 ms 65112 KB Output is correct
13 Correct 1273 ms 182940 KB Output is correct
14 Correct 632 ms 223668 KB Output is correct
15 Correct 1754 ms 175488 KB Output is correct
16 Correct 2480 ms 216680 KB Output is correct
17 Correct 2256 ms 186908 KB Output is correct
18 Correct 2410 ms 186360 KB Output is correct
19 Correct 2143 ms 210356 KB Output is correct
20 Correct 1728 ms 185872 KB Output is correct
21 Correct 2755 ms 219084 KB Output is correct
22 Correct 2773 ms 219604 KB Output is correct
23 Correct 1806 ms 184644 KB Output is correct
24 Correct 700 ms 225620 KB Output is correct
25 Correct 2231 ms 176632 KB Output is correct
26 Correct 2802 ms 218660 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65112 KB Output is correct
2 Correct 24 ms 65372 KB Output is correct
3 Correct 57 ms 65116 KB Output is correct
4 Correct 13 ms 65116 KB Output is correct
5 Correct 21 ms 65208 KB Output is correct
6 Correct 15 ms 65116 KB Output is correct
7 Correct 2166 ms 182996 KB Output is correct
8 Correct 1878 ms 207876 KB Output is correct
9 Correct 1136 ms 183792 KB Output is correct
10 Correct 2425 ms 217884 KB Output is correct
11 Correct 2420 ms 216660 KB Output is correct
12 Correct 12 ms 65112 KB Output is correct
13 Correct 1273 ms 182940 KB Output is correct
14 Correct 632 ms 223668 KB Output is correct
15 Correct 1754 ms 175488 KB Output is correct
16 Correct 2480 ms 216680 KB Output is correct
17 Correct 2256 ms 186908 KB Output is correct
18 Correct 2410 ms 186360 KB Output is correct
19 Correct 2143 ms 210356 KB Output is correct
20 Correct 1728 ms 185872 KB Output is correct
21 Correct 2755 ms 219084 KB Output is correct
22 Correct 2773 ms 219604 KB Output is correct
23 Correct 1806 ms 184644 KB Output is correct
24 Correct 700 ms 225620 KB Output is correct
25 Correct 2231 ms 176632 KB Output is correct
26 Correct 2802 ms 218660 KB Output is correct
27 Correct 4745 ms 204112 KB Output is correct
28 Correct 5902 ms 205976 KB Output is correct
29 Correct 8298 ms 232576 KB Output is correct
30 Correct 2770 ms 190780 KB Output is correct
31 Execution timed out 9026 ms 178100 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65112 KB Output is correct
2 Correct 24 ms 65372 KB Output is correct
3 Correct 57 ms 65116 KB Output is correct
4 Correct 13 ms 65116 KB Output is correct
5 Correct 21 ms 65208 KB Output is correct
6 Correct 15 ms 65116 KB Output is correct
7 Correct 2166 ms 182996 KB Output is correct
8 Correct 1878 ms 207876 KB Output is correct
9 Correct 1136 ms 183792 KB Output is correct
10 Correct 2425 ms 217884 KB Output is correct
11 Correct 2420 ms 216660 KB Output is correct
12 Correct 12 ms 65112 KB Output is correct
13 Correct 1273 ms 182940 KB Output is correct
14 Correct 632 ms 223668 KB Output is correct
15 Correct 1754 ms 175488 KB Output is correct
16 Correct 2480 ms 216680 KB Output is correct
17 Correct 2256 ms 186908 KB Output is correct
18 Correct 2410 ms 186360 KB Output is correct
19 Correct 2143 ms 210356 KB Output is correct
20 Correct 1728 ms 185872 KB Output is correct
21 Correct 2755 ms 219084 KB Output is correct
22 Correct 2773 ms 219604 KB Output is correct
23 Correct 1806 ms 184644 KB Output is correct
24 Correct 700 ms 225620 KB Output is correct
25 Correct 2231 ms 176632 KB Output is correct
26 Correct 2802 ms 218660 KB Output is correct
27 Correct 4745 ms 204112 KB Output is correct
28 Correct 5902 ms 205976 KB Output is correct
29 Correct 8298 ms 232576 KB Output is correct
30 Correct 2770 ms 190780 KB Output is correct
31 Execution timed out 9026 ms 178100 KB Time limit exceeded
32 Halted 0 ms 0 KB -