oj.uz

Submission #917936

# Submission time Handle Problem Language Result Execution time Memory
917936 2024-01-29T06:24:48 Z Equinox Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 154960 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
//typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 10010
#define MOD 1000000007

struct edge{
    ll x,w,c;
};

ll n,m,s,q,dist[100];
vector<edge> g[100];

void dijkstra(ll u, ll t){
    for(int i=1;i<=n;i++){
        dist[i] = (ll)1e18;
    }
    dist[u] = 0;
    priority_queue<pll> pq;
    pq.push({0,u});
    while(!pq.empty()){
        ll cur = pq.top().ss, len = -pq.top().ff;
        pq.pop();
        if(dist[cur]<len) continue;
        for(auto i:g[cur]){
            ll nx = i.x, l = i.w, c = i.c;
            ll w = l;
            if((len+t)%s>c-l) w += (s-(len+t)%s);
            if(len+w<dist[nx]){
                dist[nx] = len+w;
                pq.push({-dist[nx],nx});
            }
        }
    }
}

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; q = Q; s = S;
    for(int i=0;i<m;i++){
        g[A[i]+1].push_back({B[i]+1,L[i],C[i]});
        g[B[i]+1].push_back({A[i]+1,L[i],C[i]});
    }

    vector<ll> ans;
    for(int i=0;i<q;i++){
        ll u = U[i]+1, v = V[i]+1, t = T[i];
        dijkstra(u,t);
        ans.push_back(dist[v]);
    }

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65112 KB Output is correct
2 Correct 17 ms 65212 KB Output is correct
3 Correct 25 ms 65116 KB Output is correct
4 Correct 11 ms 64984 KB Output is correct
5 Correct 19 ms 65112 KB Output is correct
6 Correct 12 ms 65112 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9037 ms 154960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65112 KB Output is correct
2 Correct 17 ms 65212 KB Output is correct
3 Correct 25 ms 65116 KB Output is correct
4 Correct 11 ms 64984 KB Output is correct
5 Correct 19 ms 65112 KB Output is correct
6 Correct 12 ms 65112 KB Output is correct
7 Execution timed out 9037 ms 154960 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65112 KB Output is correct
2 Correct 17 ms 65212 KB Output is correct
3 Correct 25 ms 65116 KB Output is correct
4 Correct 11 ms 64984 KB Output is correct
5 Correct 19 ms 65112 KB Output is correct
6 Correct 12 ms 65112 KB Output is correct
7 Execution timed out 9037 ms 154960 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65112 KB Output is correct
2 Correct 17 ms 65212 KB Output is correct
3 Correct 25 ms 65116 KB Output is correct
4 Correct 11 ms 64984 KB Output is correct
5 Correct 19 ms 65112 KB Output is correct
6 Correct 12 ms 65112 KB Output is correct
7 Execution timed out 9037 ms 154960 KB Time limit exceeded
8 Halted 0 ms 0 KB -