Submission #48355

#	Time	Username	Problem	Language	Result	Execution time	Memory
48355		maksim_gaponov	Factories (JOI14_factories)	C++14	15 / 100	5822 ms	113936 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;
typedef long long ll;
/*
void openFiles() {
#ifdef KEK
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif
}
*/
void IOoptimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int MAXN = 5e3 + 10;
const ll INF = 1e17;
vector<pair<int, ll>> g[MAXN];
int n;
int type[MAXN];
ll dist[MAXN];

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

long long Query(int S, int X[], int T, int Y[]) {
    memset(type, 0, sizeof(type));
    for (int i = 0; i < T; i++) {
        type[Y[i]] = 1;
    }
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }
    set<pair<ll, int>> q;
    for (int i = 0; i < S; i++) {
        dist[X[i]] = 0;
        q.insert({dist[X[i]], X[i]});
    }
    while (!q.empty()) {
        int cur = q.begin()->second;
        q.erase(q.begin());
        if (type[cur] == 1) {
            return dist[cur];
        }
        for (auto v : g[cur]) {
            if (dist[v.first] > dist[cur] + v.second) {
                q.erase({dist[v.first], v.first});
                dist[v.first] = dist[cur] + v.second;
                q.insert({dist[v.first], v.first});
            }
        }
    }
    return INF;
}

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