oj.uz

답안 #256884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256884 2020-08-03T10:56:31 Z TeaTime 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 380416 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]) {
		if (!used[to.first]) {
			decomp(cntr(to.first, sizes[to.first]));
		}
	}
}

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 1018 ms 11016 KB Output is correct
3 Correct 1320 ms 11256 KB Output is correct
4 Correct 1206 ms 20088 KB Output is correct
5 Correct 1476 ms 20472 KB Output is correct
6 Correct 530 ms 18864 KB Output is correct
7 Correct 1269 ms 19960 KB Output is correct
8 Correct 1430 ms 19824 KB Output is correct
9 Correct 1502 ms 20460 KB Output is correct
10 Correct 518 ms 18848 KB Output is correct
11 Correct 1276 ms 20132 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 3740 ms 201788 KB Output is correct
3 Correct 5225 ms 300920 KB Output is correct
4 Correct 1390 ms 123864 KB Output is correct
5 Correct 6615 ms 380416 KB Output is correct
6 Correct 6174 ms 318676 KB Output is correct
7 Correct 3228 ms 68560 KB Output is correct
8 Correct 891 ms 44384 KB Output is correct
9 Correct 3254 ms 79144 KB Output is correct
10 Correct 3294 ms 69624 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1024 KB Output is correct
2 Correct 1018 ms 11016 KB Output is correct
3 Correct 1320 ms 11256 KB Output is correct
4 Correct 1206 ms 20088 KB Output is correct
5 Correct 1476 ms 20472 KB Output is correct
6 Correct 530 ms 18864 KB Output is correct
7 Correct 1269 ms 19960 KB Output is correct
8 Correct 1430 ms 19824 KB Output is correct
9 Correct 1502 ms 20460 KB Output is correct
10 Correct 518 ms 18848 KB Output is correct
11 Correct 1276 ms 20132 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 3740 ms 201788 KB Output is correct
14 Correct 5225 ms 300920 KB Output is correct
15 Correct 1390 ms 123864 KB Output is correct
16 Correct 6615 ms 380416 KB Output is correct
17 Correct 6174 ms 318676 KB Output is correct
18 Correct 3228 ms 68560 KB Output is correct
19 Correct 891 ms 44384 KB Output is correct
20 Correct 3254 ms 79144 KB Output is correct
21 Correct 3294 ms 69624 KB Output is correct
22 Correct 6553 ms 213524 KB Output is correct
23 Correct 6512 ms 219980 KB Output is correct
24 Execution timed out 8106 ms 286684 KB Time limit exceeded
25 Halted 0 ms 0 KB -