oj.uz

Submission #1063425

# Submission time Handle Problem Language Result Execution time Memory
1063425 2024-08-17T18:26:05 Z vjudge1 Factories (JOI14_factories) C++17
15 / 100
 2686 ms 46160 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(100005);

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[100005];
    for(int i = 0; i < 100005; ++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 41 ms 3840 KB Output is correct
2 Correct 2539 ms 21340 KB Output is correct
3 Correct 2542 ms 21344 KB Output is correct
4 Correct 1927 ms 21476 KB Output is correct
5 Correct 1625 ms 21272 KB Output is correct
6 Correct 2686 ms 21720 KB Output is correct
7 Correct 2518 ms 21312 KB Output is correct
8 Correct 2350 ms 21324 KB Output is correct
9 Correct 1523 ms 21644 KB Output is correct
10 Correct 2657 ms 21492 KB Output is correct
11 Correct 2444 ms 21328 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3676 KB Output is correct
2 Runtime error 212 ms 46160 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3840 KB Output is correct
2 Correct 2539 ms 21340 KB Output is correct
3 Correct 2542 ms 21344 KB Output is correct
4 Correct 1927 ms 21476 KB Output is correct
5 Correct 1625 ms 21272 KB Output is correct
6 Correct 2686 ms 21720 KB Output is correct
7 Correct 2518 ms 21312 KB Output is correct
8 Correct 2350 ms 21324 KB Output is correct
9 Correct 1523 ms 21644 KB Output is correct
10 Correct 2657 ms 21492 KB Output is correct
11 Correct 2444 ms 21328 KB Output is correct
12 Correct 46 ms 3676 KB Output is correct
13 Runtime error 212 ms 46160 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -