oj.uz

Submission #908802

# Submission time Handle Problem Language Result Execution time Memory
908802 2024-01-16T22:08:48 Z alexander707070 Escape Route (JOI21_escape_route) C++17
35 / 100
 9000 ms 224776 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;
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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65008 KB Output is correct
2 Correct 23 ms 65204 KB Output is correct
3 Correct 79 ms 65116 KB Output is correct
4 Correct 11 ms 65116 KB Output is correct
5 Correct 22 ms 65116 KB Output is correct
6 Correct 15 ms 65188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2720 ms 183644 KB Output is correct
2 Correct 2554 ms 206008 KB Output is correct
3 Correct 1229 ms 183744 KB Output is correct
4 Correct 3185 ms 216924 KB Output is correct
5 Correct 3164 ms 217960 KB Output is correct
6 Correct 13 ms 65112 KB Output is correct
7 Correct 1409 ms 182384 KB Output is correct
8 Correct 625 ms 223184 KB Output is correct
9 Correct 2045 ms 174504 KB Output is correct
10 Correct 3233 ms 215704 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65008 KB Output is correct
2 Correct 23 ms 65204 KB Output is correct
3 Correct 79 ms 65116 KB Output is correct
4 Correct 11 ms 65116 KB Output is correct
5 Correct 22 ms 65116 KB Output is correct
6 Correct 15 ms 65188 KB Output is correct
7 Correct 2720 ms 183644 KB Output is correct
8 Correct 2554 ms 206008 KB Output is correct
9 Correct 1229 ms 183744 KB Output is correct
10 Correct 3185 ms 216924 KB Output is correct
11 Correct 3164 ms 217960 KB Output is correct
12 Correct 13 ms 65112 KB Output is correct
13 Correct 1409 ms 182384 KB Output is correct
14 Correct 625 ms 223184 KB Output is correct
15 Correct 2045 ms 174504 KB Output is correct
16 Correct 3233 ms 215704 KB Output is correct
17 Correct 2583 ms 186608 KB Output is correct
18 Correct 3001 ms 185604 KB Output is correct
19 Correct 2885 ms 210592 KB Output is correct
20 Correct 1861 ms 184880 KB Output is correct
21 Correct 3514 ms 219804 KB Output is correct
22 Correct 3518 ms 218380 KB Output is correct
23 Correct 1934 ms 185380 KB Output is correct
24 Correct 733 ms 224776 KB Output is correct
25 Correct 2555 ms 176376 KB Output is correct
26 Correct 3550 ms 219960 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65008 KB Output is correct
2 Correct 23 ms 65204 KB Output is correct
3 Correct 79 ms 65116 KB Output is correct
4 Correct 11 ms 65116 KB Output is correct
5 Correct 22 ms 65116 KB Output is correct
6 Correct 15 ms 65188 KB Output is correct
7 Correct 2720 ms 183644 KB Output is correct
8 Correct 2554 ms 206008 KB Output is correct
9 Correct 1229 ms 183744 KB Output is correct
10 Correct 3185 ms 216924 KB Output is correct
11 Correct 3164 ms 217960 KB Output is correct
12 Correct 13 ms 65112 KB Output is correct
13 Correct 1409 ms 182384 KB Output is correct
14 Correct 625 ms 223184 KB Output is correct
15 Correct 2045 ms 174504 KB Output is correct
16 Correct 3233 ms 215704 KB Output is correct
17 Correct 2583 ms 186608 KB Output is correct
18 Correct 3001 ms 185604 KB Output is correct
19 Correct 2885 ms 210592 KB Output is correct
20 Correct 1861 ms 184880 KB Output is correct
21 Correct 3514 ms 219804 KB Output is correct
22 Correct 3518 ms 218380 KB Output is correct
23 Correct 1934 ms 185380 KB Output is correct
24 Correct 733 ms 224776 KB Output is correct
25 Correct 2555 ms 176376 KB Output is correct
26 Correct 3550 ms 219960 KB Output is correct
27 Correct 7187 ms 203452 KB Output is correct
28 Execution timed out 9097 ms 157592 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65008 KB Output is correct
2 Correct 23 ms 65204 KB Output is correct
3 Correct 79 ms 65116 KB Output is correct
4 Correct 11 ms 65116 KB Output is correct
5 Correct 22 ms 65116 KB Output is correct
6 Correct 15 ms 65188 KB Output is correct
7 Correct 2720 ms 183644 KB Output is correct
8 Correct 2554 ms 206008 KB Output is correct
9 Correct 1229 ms 183744 KB Output is correct
10 Correct 3185 ms 216924 KB Output is correct
11 Correct 3164 ms 217960 KB Output is correct
12 Correct 13 ms 65112 KB Output is correct
13 Correct 1409 ms 182384 KB Output is correct
14 Correct 625 ms 223184 KB Output is correct
15 Correct 2045 ms 174504 KB Output is correct
16 Correct 3233 ms 215704 KB Output is correct
17 Correct 2583 ms 186608 KB Output is correct
18 Correct 3001 ms 185604 KB Output is correct
19 Correct 2885 ms 210592 KB Output is correct
20 Correct 1861 ms 184880 KB Output is correct
21 Correct 3514 ms 219804 KB Output is correct
22 Correct 3518 ms 218380 KB Output is correct
23 Correct 1934 ms 185380 KB Output is correct
24 Correct 733 ms 224776 KB Output is correct
25 Correct 2555 ms 176376 KB Output is correct
26 Correct 3550 ms 219960 KB Output is correct
27 Correct 7187 ms 203452 KB Output is correct
28 Execution timed out 9097 ms 157592 KB Time limit exceeded
29 Halted 0 ms 0 KB -