Submission #62367

#	Time	Username	Problem	Language	Result	Execution time	Memory
62367		andy627	Factories (JOI14_factories)	C++17	0 / 100	73 ms	13632 KiB

factories

#include "factories.h"

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define LL long long
#define pii pair<int,int>
#define pil pair<int,LL>
#define plii pair<LL,pii>
#define ff first
#define ss second
#define INF (LL)9e18
using namespace std;

int n;
LL dist[555555];
vector<pil> edge[555555];

priority_queue<plii,vector<plii>,greater<plii> > pq;

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

long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0;i<n;i++) dist[i]=INF;
    for(int i=0;i<T;i++) pq.push({0,{Y[i],i}}),dist[Y[i]]=0;

    while(!pq.empty()){
        int p=pq.top().ss.ff;
        int pd=pq.top().ff;
        int pi=pq.top().ss.ss;
        pq.pop();

        for(int i=0;i<edge[p].size();i++){
            if(dist[edge[p][i].ff]>dist[p]+edge[p][i].ss){
                dist[edge[p][i].ff]=dist[p]+edge[p][i].ss;
                pq.push({dist[edge[p][i].ff],{edge[p][i].ff,pi}});
            }
        }
    }

    LL ans=0;
    for(int i=0;i<S;i++) ans+=dist[X[i]];

    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<edge[p].size();i++){
                     ~^~~~~~~~~~~~~~~
factories.cpp:36:13: warning: unused variable 'pd' [-Wunused-variable]
         int pd=pq.top().ff;
             ^~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67