oj.uz

Submission #908801

# Submission time Handle Problem Language Result Execution time Memory
908801 2024-01-16T21:57:25 Z alexander707070 Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 242100 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;
 
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++;
    q.push({t,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 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;
            q.push({dst[v[minv][i].to],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:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i=0;i<v[minv].size();i++){
      |                     ~^~~~~~~~~~~~~~~
escape_route.cpp: In function 'void query(int, long long int)':
escape_route.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         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 65116 KB Output is correct
2 Correct 24 ms 65116 KB Output is correct
3 Correct 79 ms 65112 KB Output is correct
4 Correct 14 ms 65372 KB Output is correct
5 Correct 23 ms 65116 KB Output is correct
6 Correct 16 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2240 ms 140000 KB Output is correct
2 Correct 1907 ms 154968 KB Output is correct
3 Correct 1170 ms 182740 KB Output is correct
4 Correct 2343 ms 217828 KB Output is correct
5 Correct 2292 ms 216228 KB Output is correct
6 Correct 12 ms 65116 KB Output is correct
7 Correct 1375 ms 181928 KB Output is correct
8 Correct 612 ms 223084 KB Output is correct
9 Correct 1859 ms 174108 KB Output is correct
10 Correct 2341 ms 217756 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65116 KB Output is correct
2 Correct 24 ms 65116 KB Output is correct
3 Correct 79 ms 65112 KB Output is correct
4 Correct 14 ms 65372 KB Output is correct
5 Correct 23 ms 65116 KB Output is correct
6 Correct 16 ms 65116 KB Output is correct
7 Correct 2240 ms 140000 KB Output is correct
8 Correct 1907 ms 154968 KB Output is correct
9 Correct 1170 ms 182740 KB Output is correct
10 Correct 2343 ms 217828 KB Output is correct
11 Correct 2292 ms 216228 KB Output is correct
12 Correct 12 ms 65116 KB Output is correct
13 Correct 1375 ms 181928 KB Output is correct
14 Correct 612 ms 223084 KB Output is correct
15 Correct 1859 ms 174108 KB Output is correct
16 Correct 2341 ms 217756 KB Output is correct
17 Correct 2372 ms 185236 KB Output is correct
18 Correct 2478 ms 184404 KB Output is correct
19 Correct 2146 ms 210044 KB Output is correct
20 Correct 1773 ms 185624 KB Output is correct
21 Correct 2654 ms 219804 KB Output is correct
22 Correct 2617 ms 220312 KB Output is correct
23 Correct 1868 ms 183864 KB Output is correct
24 Correct 711 ms 225544 KB Output is correct
25 Correct 2331 ms 175364 KB Output is correct
26 Correct 2708 ms 217952 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65116 KB Output is correct
2 Correct 24 ms 65116 KB Output is correct
3 Correct 79 ms 65112 KB Output is correct
4 Correct 14 ms 65372 KB Output is correct
5 Correct 23 ms 65116 KB Output is correct
6 Correct 16 ms 65116 KB Output is correct
7 Correct 2240 ms 140000 KB Output is correct
8 Correct 1907 ms 154968 KB Output is correct
9 Correct 1170 ms 182740 KB Output is correct
10 Correct 2343 ms 217828 KB Output is correct
11 Correct 2292 ms 216228 KB Output is correct
12 Correct 12 ms 65116 KB Output is correct
13 Correct 1375 ms 181928 KB Output is correct
14 Correct 612 ms 223084 KB Output is correct
15 Correct 1859 ms 174108 KB Output is correct
16 Correct 2341 ms 217756 KB Output is correct
17 Correct 2372 ms 185236 KB Output is correct
18 Correct 2478 ms 184404 KB Output is correct
19 Correct 2146 ms 210044 KB Output is correct
20 Correct 1773 ms 185624 KB Output is correct
21 Correct 2654 ms 219804 KB Output is correct
22 Correct 2617 ms 220312 KB Output is correct
23 Correct 1868 ms 183864 KB Output is correct
24 Correct 711 ms 225544 KB Output is correct
25 Correct 2331 ms 175364 KB Output is correct
26 Correct 2708 ms 217952 KB Output is correct
27 Correct 5542 ms 203144 KB Output is correct
28 Correct 6414 ms 205216 KB Output is correct
29 Correct 6204 ms 232904 KB Output is correct
30 Correct 2945 ms 189276 KB Output is correct
31 Correct 7253 ms 241476 KB Output is correct
32 Correct 7221 ms 242100 KB Output is correct
33 Correct 902 ms 228188 KB Output is correct
34 Correct 5318 ms 192632 KB Output is correct
35 Correct 6980 ms 239808 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65116 KB Output is correct
2 Correct 24 ms 65116 KB Output is correct
3 Correct 79 ms 65112 KB Output is correct
4 Correct 14 ms 65372 KB Output is correct
5 Correct 23 ms 65116 KB Output is correct
6 Correct 16 ms 65116 KB Output is correct
7 Correct 2240 ms 140000 KB Output is correct
8 Correct 1907 ms 154968 KB Output is correct
9 Correct 1170 ms 182740 KB Output is correct
10 Correct 2343 ms 217828 KB Output is correct
11 Correct 2292 ms 216228 KB Output is correct
12 Correct 12 ms 65116 KB Output is correct
13 Correct 1375 ms 181928 KB Output is correct
14 Correct 612 ms 223084 KB Output is correct
15 Correct 1859 ms 174108 KB Output is correct
16 Correct 2341 ms 217756 KB Output is correct
17 Correct 2372 ms 185236 KB Output is correct
18 Correct 2478 ms 184404 KB Output is correct
19 Correct 2146 ms 210044 KB Output is correct
20 Correct 1773 ms 185624 KB Output is correct
21 Correct 2654 ms 219804 KB Output is correct
22 Correct 2617 ms 220312 KB Output is correct
23 Correct 1868 ms 183864 KB Output is correct
24 Correct 711 ms 225544 KB Output is correct
25 Correct 2331 ms 175364 KB Output is correct
26 Correct 2708 ms 217952 KB Output is correct
27 Correct 5542 ms 203144 KB Output is correct
28 Correct 6414 ms 205216 KB Output is correct
29 Correct 6204 ms 232904 KB Output is correct
30 Correct 2945 ms 189276 KB Output is correct
31 Correct 7253 ms 241476 KB Output is correct
32 Correct 7221 ms 242100 KB Output is correct
33 Correct 902 ms 228188 KB Output is correct
34 Correct 5318 ms 192632 KB Output is correct
35 Correct 6980 ms 239808 KB Output is correct
36 Execution timed out 9077 ms 158036 KB Time limit exceeded
37 Halted 0 ms 0 KB -