oj.uz

Submission #48355

# Submission time Handle Problem Language Result Execution time Memory
48355 2018-05-11T19:43:04 Z maksim_gaponov Factories (JOI14_factories) C++14
15 / 100
 5822 ms 113936 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 760 KB Output is correct
2 Correct 2683 ms 9108 KB Output is correct
3 Correct 807 ms 18480 KB Output is correct
4 Correct 1099 ms 28216 KB Output is correct
5 Correct 1509 ms 37732 KB Output is correct
6 Correct 5822 ms 47616 KB Output is correct
7 Correct 794 ms 56632 KB Output is correct
8 Correct 2654 ms 66084 KB Output is correct
9 Correct 1499 ms 75716 KB Output is correct
10 Correct 5662 ms 85440 KB Output is correct
11 Correct 788 ms 94564 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 94564 KB Output is correct
2 Runtime error 415 ms 108268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 530 ms 113936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -