oj.uz

Submission #978556

# Submission time Handle Problem Language Result Execution time Memory
978556 2024-05-09T10:31:10 Z tnknguyen_ Factories (JOI14_factories) C++14
15 / 100
 8000 ms 59476 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define endl '\n' 
#define ll long long 
#define len(s) (int)s.size() 
#define pii pair<int, int>
//#define int long long 

const int MX = 5e5 + 5;
const int LG = 19;
vector<pii> gr[MX];
ll up[LG][MX], f[LG][MX], dep[MX];
int n, q;

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i=0; i<n; ++i){
        int u = A[i], v = B[i], c = D[i];
        ++u, ++v;
        gr[u].push_back({v, c});
        gr[v].push_back({u, c});
    }

    //dfs(1, 1);
}

ll Query(int S, int X[], int T, int Y[]){
    ll ans = 1e18;

    vector<ll> dist(n + 5, 1e18);
    priority_queue<pair<ll, ll>> q;
    for(int i=0; i<S; ++i){
        dist[X[i] + 1] = 0;
        q.push({0, X[i] + 1});
    }

    while(q.size()){
        ll w, u;
        tie(w, u) = q.top();
        w = -w;
        q.pop();

        for(pii e : gr[u]){
            ll v, c;
            tie(v, c) = e;
            if(w + c < dist[v]){
                dist[v] = w + c;
                q.push({-dist[v], v});
            }
        }
    }

    for(int i=0; i<T; ++i){
        ans = min(ans, dist[Y[i] + 1]);
    }

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 29020 KB Output is correct
2 Correct 2343 ms 33536 KB Output is correct
3 Correct 2320 ms 42992 KB Output is correct
4 Correct 1790 ms 43132 KB Output is correct
5 Correct 1354 ms 42984 KB Output is correct
6 Correct 2851 ms 43580 KB Output is correct
7 Correct 2319 ms 42992 KB Output is correct
8 Correct 2206 ms 42992 KB Output is correct
9 Correct 1281 ms 42992 KB Output is correct
10 Correct 2805 ms 43500 KB Output is correct
11 Correct 2347 ms 42996 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29020 KB Output is correct
2 Execution timed out 8050 ms 59476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 29020 KB Output is correct
2 Correct 2343 ms 33536 KB Output is correct
3 Correct 2320 ms 42992 KB Output is correct
4 Correct 1790 ms 43132 KB Output is correct
5 Correct 1354 ms 42984 KB Output is correct
6 Correct 2851 ms 43580 KB Output is correct
7 Correct 2319 ms 42992 KB Output is correct
8 Correct 2206 ms 42992 KB Output is correct
9 Correct 1281 ms 42992 KB Output is correct
10 Correct 2805 ms 43500 KB Output is correct
11 Correct 2347 ms 42996 KB Output is correct
12 Correct 22 ms 29020 KB Output is correct
13 Execution timed out 8050 ms 59476 KB Time limit exceeded
14 Halted 0 ms 0 KB -