Submission #821109

#	Time	Username	Problem	Language	Result	Execution time	Memory
821109		Alihan_8	공장들 (JOI14_factories)	C++17	15 / 100	8086 ms	66204 KiB

factories

#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 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67