Submission #978556

#	Time	Username	Problem	Language	Result	Execution time	Memory
978556		tnknguyen_	Factories (JOI14_factories)	C++14	15 / 100	8050 ms	59476 KiB

factories

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