oj.uz

답안 #256895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256895 2020-08-03T11:08:01 Z TeaTime 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 362820 KB 
#include "factories.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_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;
unordered_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 13 ms 768 KB Output is correct
2 Correct 547 ms 9976 KB Output is correct
3 Correct 638 ms 10416 KB Output is correct
4 Correct 518 ms 10488 KB Output is correct
5 Correct 633 ms 10856 KB Output is correct
6 Correct 400 ms 9464 KB Output is correct
7 Correct 629 ms 10360 KB Output is correct
8 Correct 641 ms 10488 KB Output is correct
9 Correct 653 ms 11148 KB Output is correct
10 Correct 404 ms 9516 KB Output is correct
11 Correct 642 ms 10476 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3243 ms 201720 KB Output is correct
3 Correct 4492 ms 300648 KB Output is correct
4 Correct 1433 ms 105556 KB Output is correct
5 Correct 4908 ms 362820 KB Output is correct
6 Correct 4588 ms 301932 KB Output is correct
7 Correct 2008 ms 55072 KB Output is correct
8 Correct 779 ms 30572 KB Output is correct
9 Correct 2168 ms 65316 KB Output is correct
10 Correct 2051 ms 55772 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 768 KB Output is correct
2 Correct 547 ms 9976 KB Output is correct
3 Correct 638 ms 10416 KB Output is correct
4 Correct 518 ms 10488 KB Output is correct
5 Correct 633 ms 10856 KB Output is correct
6 Correct 400 ms 9464 KB Output is correct
7 Correct 629 ms 10360 KB Output is correct
8 Correct 641 ms 10488 KB Output is correct
9 Correct 653 ms 11148 KB Output is correct
10 Correct 404 ms 9516 KB Output is correct
11 Correct 642 ms 10476 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3243 ms 201720 KB Output is correct
14 Correct 4492 ms 300648 KB Output is correct
15 Correct 1433 ms 105556 KB Output is correct
16 Correct 4908 ms 362820 KB Output is correct
17 Correct 4588 ms 301932 KB Output is correct
18 Correct 2008 ms 55072 KB Output is correct
19 Correct 779 ms 30572 KB Output is correct
20 Correct 2168 ms 65316 KB Output is correct
21 Correct 2051 ms 55772 KB Output is correct
22 Correct 4270 ms 207652 KB Output is correct
23 Execution timed out 8028 ms 211624 KB Time limit exceeded
24 Halted 0 ms 0 KB -