oj.uz

Submission #908806

# Submission time Handle Problem Language Result Execution time Memory
908806 2024-01-16T22:26:29 Z alexander707070 Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 243308 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];
 
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]);
            }

            for(int f=1;f<=n;f++){
                if(mins==lim[parent[f]][f]-cost[parent[f]][f]-dst[parent[f]]){

                    for(int k=0;k<v[f].size();k++){
                        if(v[f][k].to==parent[f]){
                            swap(v[f][k],v[f][v[f].size()-1]);
                            v[f].pop_back(); break;
                        }
                    }

                    for(int k=0;k<v[parent[f]].size();k++){
                        if(v[parent[f]][k].to==f){
                            swap(v[parent[f]][k],v[parent[f]][v[parent[f]].size()-1]);
                            v[parent[f]].pop_back(); break;
                        }
                    }
                }
            }
 
            dists[i].push_back({w+mins,curr});
            if(mins==inf)break;
            w+=mins+1;
        }

        for(int f=1;f<=n;f++){
            v[f].clear();
        }

        for(int i=1;i<=m;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<=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++){
      |                     ~^~~~~~~~~~~~~~~
escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, long long int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
escape_route.cpp:151:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |                     for(int k=0;k<v[f].size();k++){
      |                                 ~^~~~~~~~~~~~
escape_route.cpp:158:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |                     for(int k=0;k<v[parent[f]].size();k++){
      |                                 ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 65116 KB Output is correct
2 Correct 25 ms 65116 KB Output is correct
3 Correct 78 ms 65152 KB Output is correct
4 Correct 14 ms 65116 KB Output is correct
5 Correct 24 ms 65112 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 2186 ms 183456 KB Output is correct
2 Correct 1741 ms 207616 KB Output is correct
3 Correct 1162 ms 184328 KB Output is correct
4 Correct 2240 ms 216576 KB Output is correct
5 Correct 2233 ms 217612 KB Output is correct
6 Correct 13 ms 65112 KB Output is correct
7 Correct 1317 ms 182032 KB Output is correct
8 Correct 624 ms 223244 KB Output is correct
9 Correct 1829 ms 173364 KB Output is correct
10 Correct 2303 ms 217436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 65116 KB Output is correct
2 Correct 25 ms 65116 KB Output is correct
3 Correct 78 ms 65152 KB Output is correct
4 Correct 14 ms 65116 KB Output is correct
5 Correct 24 ms 65112 KB Output is correct
6 Correct 16 ms 65116 KB Output is correct
7 Correct 2186 ms 183456 KB Output is correct
8 Correct 1741 ms 207616 KB Output is correct
9 Correct 1162 ms 184328 KB Output is correct
10 Correct 2240 ms 216576 KB Output is correct
11 Correct 2233 ms 217612 KB Output is correct
12 Correct 13 ms 65112 KB Output is correct
13 Correct 1317 ms 182032 KB Output is correct
14 Correct 624 ms 223244 KB Output is correct
15 Correct 1829 ms 173364 KB Output is correct
16 Correct 2303 ms 217436 KB Output is correct
17 Correct 2331 ms 185084 KB Output is correct
18 Correct 2421 ms 185316 KB Output is correct
19 Correct 2076 ms 209480 KB Output is correct
20 Correct 1845 ms 186384 KB Output is correct
21 Correct 2587 ms 220376 KB Output is correct
22 Correct 2574 ms 218812 KB Output is correct
23 Correct 1867 ms 184764 KB Output is correct
24 Correct 704 ms 226452 KB Output is correct
25 Correct 2342 ms 175564 KB Output is correct
26 Correct 2623 ms 219956 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 65116 KB Output is correct
2 Correct 25 ms 65116 KB Output is correct
3 Correct 78 ms 65152 KB Output is correct
4 Correct 14 ms 65116 KB Output is correct
5 Correct 24 ms 65112 KB Output is correct
6 Correct 16 ms 65116 KB Output is correct
7 Correct 2186 ms 183456 KB Output is correct
8 Correct 1741 ms 207616 KB Output is correct
9 Correct 1162 ms 184328 KB Output is correct
10 Correct 2240 ms 216576 KB Output is correct
11 Correct 2233 ms 217612 KB Output is correct
12 Correct 13 ms 65112 KB Output is correct
13 Correct 1317 ms 182032 KB Output is correct
14 Correct 624 ms 223244 KB Output is correct
15 Correct 1829 ms 173364 KB Output is correct
16 Correct 2303 ms 217436 KB Output is correct
17 Correct 2331 ms 185084 KB Output is correct
18 Correct 2421 ms 185316 KB Output is correct
19 Correct 2076 ms 209480 KB Output is correct
20 Correct 1845 ms 186384 KB Output is correct
21 Correct 2587 ms 220376 KB Output is correct
22 Correct 2574 ms 218812 KB Output is correct
23 Correct 1867 ms 184764 KB Output is correct
24 Correct 704 ms 226452 KB Output is correct
25 Correct 2342 ms 175564 KB Output is correct
26 Correct 2623 ms 219956 KB Output is correct
27 Correct 5128 ms 204672 KB Output is correct
28 Correct 5668 ms 205244 KB Output is correct
29 Correct 5352 ms 233084 KB Output is correct
30 Correct 2920 ms 190084 KB Output is correct
31 Correct 6533 ms 241888 KB Output is correct
32 Correct 6484 ms 243308 KB Output is correct
33 Correct 926 ms 228608 KB Output is correct
34 Correct 4987 ms 191500 KB Output is correct
35 Correct 6313 ms 242776 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 65116 KB Output is correct
2 Correct 25 ms 65116 KB Output is correct
3 Correct 78 ms 65152 KB Output is correct
4 Correct 14 ms 65116 KB Output is correct
5 Correct 24 ms 65112 KB Output is correct
6 Correct 16 ms 65116 KB Output is correct
7 Correct 2186 ms 183456 KB Output is correct
8 Correct 1741 ms 207616 KB Output is correct
9 Correct 1162 ms 184328 KB Output is correct
10 Correct 2240 ms 216576 KB Output is correct
11 Correct 2233 ms 217612 KB Output is correct
12 Correct 13 ms 65112 KB Output is correct
13 Correct 1317 ms 182032 KB Output is correct
14 Correct 624 ms 223244 KB Output is correct
15 Correct 1829 ms 173364 KB Output is correct
16 Correct 2303 ms 217436 KB Output is correct
17 Correct 2331 ms 185084 KB Output is correct
18 Correct 2421 ms 185316 KB Output is correct
19 Correct 2076 ms 209480 KB Output is correct
20 Correct 1845 ms 186384 KB Output is correct
21 Correct 2587 ms 220376 KB Output is correct
22 Correct 2574 ms 218812 KB Output is correct
23 Correct 1867 ms 184764 KB Output is correct
24 Correct 704 ms 226452 KB Output is correct
25 Correct 2342 ms 175564 KB Output is correct
26 Correct 2623 ms 219956 KB Output is correct
27 Correct 5128 ms 204672 KB Output is correct
28 Correct 5668 ms 205244 KB Output is correct
29 Correct 5352 ms 233084 KB Output is correct
30 Correct 2920 ms 190084 KB Output is correct
31 Correct 6533 ms 241888 KB Output is correct
32 Correct 6484 ms 243308 KB Output is correct
33 Correct 926 ms 228608 KB Output is correct
34 Correct 4987 ms 191500 KB Output is correct
35 Correct 6313 ms 242776 KB Output is correct
36 Execution timed out 9040 ms 161008 KB Time limit exceeded
37 Halted 0 ms 0 KB -