oj.uz

Submission #1063429

# Submission time Handle Problem Language Result Execution time Memory
1063429 2024-08-17T18:27:34 Z vjudge1 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 72508 KB 
#include "factories.h"

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef pair<char, ll> ci;
typedef pair<string, ll> si;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
#define pb push_back
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
const ll inf = 10000000000000000;
#define fro front

vector<vector<ii>> x(500005);

void Init(int N, int A[], int B[], int D[]) {
    for(ll i = 0; i < N; ++i){
        x[A[i]].pb(ii(B[i], D[i]));
        x[B[i]].pb(ii(A[i], D[i]));
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = inf;
    priority_queue<ii, vector<ii>, greater<ii>> q;
    ll dist[500005];
    for(int i = 0; i < 500005; ++i){
        dist[i] = inf;
    }
    for(ll i = 0; i < S; ++i){
        q.push(ii(0, X[i]));
        dist[X[i]] = 0;
    }
    while(!q.empty()){
        ll price = q.top().fi;
        ll node = q.top().se;
        q.pop();
        if(price != dist[node]){
            continue;
        }
        for(auto e:x[node]){
            if(dist[e.fi] > dist[node] + e.se){
                q.push(ii(price + e.se, e.fi));
                dist[e.fi] = price + e.se;
            }
        }
    }
    for(int i = 0; i < T; ++i){
        ans = min(ans, dist[Y[i]]);
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 16476 KB Output is correct
2 Correct 3214 ms 31832 KB Output is correct
3 Correct 3192 ms 31692 KB Output is correct
4 Correct 2714 ms 31968 KB Output is correct
5 Correct 2228 ms 33080 KB Output is correct
6 Correct 3452 ms 33400 KB Output is correct
7 Correct 3247 ms 33528 KB Output is correct
8 Correct 3113 ms 33572 KB Output is correct
9 Correct 2322 ms 33620 KB Output is correct
10 Correct 3563 ms 33780 KB Output is correct
11 Correct 3360 ms 33608 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 16216 KB Output is correct
2 Execution timed out 8066 ms 72508 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 16476 KB Output is correct
2 Correct 3214 ms 31832 KB Output is correct
3 Correct 3192 ms 31692 KB Output is correct
4 Correct 2714 ms 31968 KB Output is correct
5 Correct 2228 ms 33080 KB Output is correct
6 Correct 3452 ms 33400 KB Output is correct
7 Correct 3247 ms 33528 KB Output is correct
8 Correct 3113 ms 33572 KB Output is correct
9 Correct 2322 ms 33620 KB Output is correct
10 Correct 3563 ms 33780 KB Output is correct
11 Correct 3360 ms 33608 KB Output is correct
12 Correct 160 ms 16216 KB Output is correct
13 Execution timed out 8066 ms 72508 KB Time limit exceeded
14 Halted 0 ms 0 KB -