oj.uz

Submission #62367

# Submission time Handle Problem Language Result Execution time Memory
62367 2018-07-28T08:45:47 Z andy627 Factories (JOI14_factories) C++17
0 / 100
 73 ms 13632 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 13632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 13632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 13632 KB Output isn't correct
2 Halted 0 ms 0 KB -