Submission #1159584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159584		PagodePaiva	Escape Route (JOI21_escape_route)	C++20	Compilation error	0 ms	0 KiB

escape_route

#include<bits/stdc++.h>
#include "escape_route.h"

using namespace std;

const long long N = 41;
const long long inf = 1e16;
long long n, m, s, q;
long long dp[N][N];
vector <array <long long, 3>> g[N];
long long dist[N];
long long last[N];

void solve(long long st){
    dp[st][st] = 0;
    for(long long i = 0;i < n;i++){
        dist[i] = inf;
    }
    dist[st] = 0;
    priority_queue <pair <long long, long long>> pq;
    pq.push({0, st});
    while(!pq.empty()){
        auto [tempo, v] = pq.top();
        pq.pop();
        tempo *= -1;
        if(tempo != dist[v]) continue;
        for(auto [x, l, c] : g[v]){
            if(dist[v]+l > c) continue;
            if(dist[v]+l < dist[x]){
                dist[x] = dist[v]+l;
                dp[st][x] = dist[x];
                pq.push({-dist[x], x});
            }
        }
    }
    return;
}

pair <long long, long long> dist2[N];
vector <long long> answer;

void solve2(long long u, long long v, long long t){
    set <long long> vertices;
    for(long long i = 0;i < n;i++){
        dist[i] = inf;
    }
    dist[u] = t;
    priority_queue <pair <long long, long long>> pq;
    pq.push({-t, u});
    while(!pq.empty()){
        auto [tempo, v] = pq.top();
        pq.pop();
        tempo *= -1;
        if(tempo != dist[v]) continue;
        vertices.insert(v);
        for(auto [x, l, c] : g[v]){
            if(dist[v]+l > c) continue;
            if(dist[v]+l < dist[x]){
                dist[x] = dist[v]+l;
                pq.push({-dist[x], x});
            }
        }
    }
    for(long long i = 0;i < n;i++){
        dist2[i] = {90, inf};
    }
    for(auto i : vertices){
        dist2[i] = {0, dist[i]};
        pq.push({-s*dist2[i].first-dist2[i].second, i});
    }
    while(!pq.empty()){
        auto [d, v] = pq.top();
        pq.pop();
        d *= -1;
        //cout << d << ' ' << v << '\n';
        if(d != dist2[v].first*s+dist2[v].second) continue;
        for(long long i = 0;i < n;i++){
            if(dp[v][i] > -1){
                if((dist2[v].first+1)*s+dp[v][i] < dist2[i].first*s+dist2[i].second){
                    dist2[i] = make_pair(dist2[v].first+1, dp[v][i]);
                    pq.push({-s*dist2[i].first-dist2[i].second, i});
                }
            }
        }
    }
    answer.push_back(dist2[v].first*s+dist2[v].second-t);
}   

std::vector<long long> calculate_necessary_time(
    long long N, long long M, long long S, long long Q, std::vector<long long> A, std::vector<long long> B,
    std::vector<long long> L, std::vector<long long> C, std::vector<long long> U,
    std::vector<long long> V, std::vector<long long> T) {
    memset(dp, -1, sizeof dp);
    n = N;
    m = M;
    s = S;
    q = Q;
    for(long long i = 0;i < m;i++){
        long long a, b, l, c;
        a = A[i];
        b = B[i];
        l = L[i];
        c = C[i];
        g[a].push_back({b, l, c});
        g[b].push_back({a, l, c});
    }
    for(long long i = 0;i < n;i++){
        solve(i);
    }
    for(int i = 0;i < q;i++){
        long long u, v, t;
        u = U[i];
        v = V[i];
        t = T[i];
        solve2(u, v, t);
    }
    return answer;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccI4J8q2.o: in function `main':
grader.cpp:(.text.startup+0x6e0): undefined reference to `calculate_necessary_time(int, int, long long, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<long long, std::allocator<long long> >, std::vector<long long, std::allocator<long long> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<long long, std::allocator<long long> >)'
collect2: error: ld returned 1 exit status