oj.uz

Submission #821109

# Submission time Handle Problem Language Result Execution time Memory
821109 2023-08-11T07:31:11 Z Alihan_8 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 66204 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

const long long inf = 1e15 + 1;

vector <pair<int,int>> g[500005];

int n;

void Init(int N, int A[], int B[], int D[]) {
    for ( int i = 0; i + 1 < N; i++ ){
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    } n = N;
}

long long Query(int S, int X[], int T, int Y[]) {
    priority_queue <pair<long long,int>> q;
    vector <long long> dis(n, inf);
    for ( int i = 0; i < S; i++ ){
        dis[X[i]] = 0;
        q.push({0, X[i]});
    }
    while ( !q.empty() ){
        auto [val, u] = q.top();
        q.pop(); val *= -1;
        if ( dis[u] != val ){
            continue;
        }
        for ( auto [v, w]: g[u] ){
            if ( chmin(dis[v], dis[u] + w) ){
                q.push({-dis[v], v});
            }

        }
    }
    long long ans = inf;
    for ( int i = 0; i < T; i++ ){
        chmin(ans, dis[Y[i]]);
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12532 KB Output is correct
2 Correct 2416 ms 29820 KB Output is correct
3 Correct 2347 ms 29784 KB Output is correct
4 Correct 1789 ms 29924 KB Output is correct
5 Correct 1316 ms 29752 KB Output is correct
6 Correct 2694 ms 30412 KB Output is correct
7 Correct 2321 ms 30020 KB Output is correct
8 Correct 2275 ms 29800 KB Output is correct
9 Correct 1297 ms 29880 KB Output is correct
10 Correct 2748 ms 30088 KB Output is correct
11 Correct 2380 ms 29892 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12176 KB Output is correct
2 Execution timed out 8086 ms 66204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12532 KB Output is correct
2 Correct 2416 ms 29820 KB Output is correct
3 Correct 2347 ms 29784 KB Output is correct
4 Correct 1789 ms 29924 KB Output is correct
5 Correct 1316 ms 29752 KB Output is correct
6 Correct 2694 ms 30412 KB Output is correct
7 Correct 2321 ms 30020 KB Output is correct
8 Correct 2275 ms 29800 KB Output is correct
9 Correct 1297 ms 29880 KB Output is correct
10 Correct 2748 ms 30088 KB Output is correct
11 Correct 2380 ms 29892 KB Output is correct
12 Correct 23 ms 12176 KB Output is correct
13 Execution timed out 8086 ms 66204 KB Time limit exceeded
14 Halted 0 ms 0 KB -