oj.uz

Submission #52203

# Submission time Handle Problem Language Result Execution time Memory
52203 2018-06-25T04:13:57 Z 윤교준(#1348) Factories (JOI14_factories) C++11
15 / 100
 2565 ms 110552 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }

const int MAXN = 5005;

vector<pii> G[MAXN];

ll d[MAXN];
bitset<MAXN> chk;

int A[MAXN], B[MAXN], C[MAXN];

int N;

void Init(int N, int A[], int B[], int D[]) {
	::N = N;
	for(int i = 0; i < N-1; i++) {
		::A[i+1] = A[i]+1;
		::B[i+1] = B[i]+1;
		::C[i+1] = D[i];
		fg(G, A[i]+1, B[i]+1, D[i]);
	}
}

long long Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < S; i++) X[i]++;
	for(int i = 0; i < T; i++) Y[i]++;

	fill(d, d+N+1, INFLL);
	chk.reset();
	
	priority_queue<pli, vector<pli>, greater<pli>> PQ;

	for(int i = 0; i < S; i++) {
		int v = X[i];
		d[v] = 0;
		PQ.push({0, v});
	}
	for(int i = 0; i < T; i++) {
		chk[Y[i]] = true;
	}

	for(; !PQ.empty();) {
		ll dst; int idx;
		tie(dst, idx) = PQ.top(); PQ.pop();
		if(d[idx] < dst) continue;
		if(chk[idx]) return dst;

		for(pii e : G[idx]) {
			ll ndst = dst + e.second;
			int nidx = e.first;

			if(d[nidx] <= ndst) continue;
			d[nidx] = ndst;
			PQ.push({ndst, nidx});
		}
	}
	return INFLL;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1056 KB Output is correct
2 Correct 1528 ms 11468 KB Output is correct
3 Correct 507 ms 20788 KB Output is correct
4 Correct 707 ms 30596 KB Output is correct
5 Correct 985 ms 39784 KB Output is correct
6 Correct 2565 ms 49684 KB Output is correct
7 Correct 665 ms 58848 KB Output is correct
8 Correct 1613 ms 68508 KB Output is correct
9 Correct 914 ms 77980 KB Output is correct
10 Correct 2409 ms 87704 KB Output is correct
11 Correct 514 ms 96736 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 96736 KB Output is correct
2 Runtime error 431 ms 110552 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 Correct 15 ms 1056 KB Output is correct
2 Correct 1528 ms 11468 KB Output is correct
3 Correct 507 ms 20788 KB Output is correct
4 Correct 707 ms 30596 KB Output is correct
5 Correct 985 ms 39784 KB Output is correct
6 Correct 2565 ms 49684 KB Output is correct
7 Correct 665 ms 58848 KB Output is correct
8 Correct 1613 ms 68508 KB Output is correct
9 Correct 914 ms 77980 KB Output is correct
10 Correct 2409 ms 87704 KB Output is correct
11 Correct 514 ms 96736 KB Output is correct
12 Correct 10 ms 96736 KB Output is correct
13 Runtime error 431 ms 110552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -