oj.uz

답안 #256887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256887 2020-08-03T11:00:27 Z TeaTime 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 307040 KB 
#include "factories.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 5e5 + 10, INF = 1e9 * 1e9;
int sizes[SZ], x[SZ], y[SZ];
bool used[SZ];
vector<vector<pair<ll, ll>>> vec;

vector<vector<pair<ll, ll>>> gr;
ll curC = 0;
vector<ll> bst;
set<ll> u;

ll sz(int v, ll dist = 0, int par = -1) {
	ll s = 1;
	vec[v].push_back({ curC, dist });

	for (auto to : gr[v]) {
		if (!used[to.first] && to.first != par) {
			s += sz(to.first, dist + to.second, v);
		}
	}

	sizes[v] = s;
	return s;
}

ll cntr(int v, int c, int par = -1) {
	for (auto to : gr[v]) {
		if (to.first != par && !used[to.first] && sizes[to.first] >= c / 2) {
			return cntr(to.first, c, v);
		}
	}

	return v;
}

void decomp(int v) {
	used[v] = 1;
	curC = v;
	sz(v);

	for (auto to : gr[v]) {
		ll c = cntr(to.first, sizes[to.first]);
		if (!used[c]) {
			decomp(c);
		}
	}
}

void Init(int N, int A[], int B[], int D[]) {
	gr.clear();
	vec.clear();
	bst.clear();
	gr.resize(N);
	vec.resize(N);
	for (int i = 0; i < N - 1; i++) {
		gr[A[i]].push_back({ B[i], D[i] });
		gr[B[i]].push_back({ A[i], D[i] });
	}

	bst.resize(N);
	for (auto &c : bst) c = INF;
	decomp(0);
}

long long Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++) {
		ll ind = X[i];
		for (auto cur : vec[ind]) {
			u.insert(cur.first);
			bst[cur.first] = min(bst[cur.first], cur.second);
		}
	}

	ll ans = INF;
	for (int i = 0; i < T; i++) {
		ll ind = Y[i];
		for (auto cur : vec[ind]) {
			ans = min(ans, bst[cur.first] + cur.second);
		}
	}
	for (auto cur : u) bst[cur] = INF;
	u.clear();
	return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1024 KB Output is correct
2 Correct 1039 ms 10896 KB Output is correct
3 Correct 1353 ms 11192 KB Output is correct
4 Correct 1231 ms 20044 KB Output is correct
5 Correct 1659 ms 20628 KB Output is correct
6 Correct 554 ms 18936 KB Output is correct
7 Correct 1344 ms 19832 KB Output is correct
8 Correct 1352 ms 19968 KB Output is correct
9 Correct 1652 ms 20600 KB Output is correct
10 Correct 559 ms 18868 KB Output is correct
11 Correct 1319 ms 19852 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 3281 ms 201916 KB Output is correct
3 Correct 5718 ms 307040 KB Output is correct
4 Execution timed out 8071 ms 89272 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1024 KB Output is correct
2 Correct 1039 ms 10896 KB Output is correct
3 Correct 1353 ms 11192 KB Output is correct
4 Correct 1231 ms 20044 KB Output is correct
5 Correct 1659 ms 20628 KB Output is correct
6 Correct 554 ms 18936 KB Output is correct
7 Correct 1344 ms 19832 KB Output is correct
8 Correct 1352 ms 19968 KB Output is correct
9 Correct 1652 ms 20600 KB Output is correct
10 Correct 559 ms 18868 KB Output is correct
11 Correct 1319 ms 19852 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 3281 ms 201916 KB Output is correct
14 Correct 5718 ms 307040 KB Output is correct
15 Execution timed out 8071 ms 89272 KB Time limit exceeded
16 Halted 0 ms 0 KB -