oj.uz

Submission #384306

# Submission time Handle Problem Language Result Execution time Memory
384306 2021-04-01T09:49:53 Z shivensinha4 Factories (JOI14_factories) C++17
100 / 100
 5141 ms 253832 KB 
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
#ifndef mlocal
#include "factories.h"
#endif
 
int n;
vector<vector<array<ll, 2>>> adjList;
vi removed, subtreeSize, centroid;
vector<ll> whiteDist;
vector<vector<ll>> centroidDist;
const ll INF = 1e15;
 
void dfs(int p, int parent) {
	for (auto i: adjList[p]) if (i[0] != parent) {
		dfs(i[0], p);
		subtreeSize[p] += subtreeSize[i[0]];
	}
	
	subtreeSize[p] += 1;
}

void noteCentroidDist(int p, int parent) {
	ll d = centroidDist[p].back();
	for (auto i: adjList[p]) if (!removed[i[0]] and i[0] != parent) {
		centroidDist[i[0]].push_back(d+i[1]);
		noteCentroidDist(i[0], p);
	}
}
 
void decompose(int p, int c) {
	int invalidChild = -1, sizeLimit = (subtreeSize[p] >> 1);
	for (auto i: adjList[p]) if (!removed[i[0]] and subtreeSize[i[0]] > sizeLimit) {
			invalidChild = i[0];
			break;
		}
	
	if (invalidChild != -1) {
		subtreeSize[p] -= subtreeSize[invalidChild];
		subtreeSize[invalidChild] += subtreeSize[p];
		return decompose(invalidChild, c);
	}
	
	removed[p] = true;
	centroid[p] = c;
	
	centroidDist[p].push_back(0);
	noteCentroidDist(p, p);
	
	for (auto i: adjList[p]) if (!removed[i[0]]) {
		centroid[i[0]] = p;
		decompose(i[0], p);
	}
}
 
vi updated;
int pt = 0;
 
void update(int p) {
	int v = p, cpt = (int) centroidDist[p].size() - 1;
	while (v != -1) {
		ll d = centroidDist[p][cpt--];
		whiteDist[v] = min(whiteDist[v], d);
		updated[pt++] = v;
		v = centroid[v];
	}
}
 
ll ans(int p) {
	ll val = INF;
	int v = p,  cpt = (int) centroidDist[p].size() - 1;
	while (v != -1) {
		val = min(val, whiteDist[v] + centroidDist[p][cpt--]);
		v = centroid[v];
	}
	return (val == 1e9 ? -1 : val);
}
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	adjList.resize(n); subtreeSize.resize(n); removed.resize(n); centroid.resize(n, -1); whiteDist.resize(n, INF); updated.resize(10*n); centroidDist.resize(n);
	for_(i, 0, n-1) {
		int a = A[i], b = B[i]; ll w = D[i];
		adjList[a].push_back({b, w});
		adjList[b].push_back({a, w});
	}
	
	dfs(0, 0);
	decompose(0, -1);
}
 
ll Query(int S, int X[], int T, int Y[]) {
	pt = 0;
	
	for_(i, 0, S) update(X[i]);
	ll val = INF;
	for_(i, 0, T) val = min(val, ans(Y[i]));
	for_(i, 0, pt) whiteDist[updated[i]] = INF;
	
	return val;
}
 
#ifdef mlocal
int main() {
	freopen("test.in", "r", stdin);
 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	int N, q;
	cin >> N >> q;
	int A[100], B[100], D[100];
	for_(i, 0, N - 1) {
		int a, b, w;
		cin >> a >> b >> w;
		A[i] = a;
		B[i] = b;
		D[i] = w;
	}
 
	Init(N, A, B, D);
 
	int X[100], Y[100];
	while (q--) {
		int S, T;
		cin >> S >> T;
		for_(i, 0, S) cin >> X[i];
		for_(i, 0, T) cin >> Y[i];
		cout << Query(S, X, T, Y) << endl;
	}
 
	return 0;
}
#endif

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 876 KB Output is correct
2 Correct 361 ms 9836 KB Output is correct
3 Correct 390 ms 9964 KB Output is correct
4 Correct 402 ms 10220 KB Output is correct
5 Correct 414 ms 10732 KB Output is correct
6 Correct 272 ms 9708 KB Output is correct
7 Correct 423 ms 10268 KB Output is correct
8 Correct 399 ms 10268 KB Output is correct
9 Correct 418 ms 10604 KB Output is correct
10 Correct 276 ms 9580 KB Output is correct
11 Correct 415 ms 10348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 2516 ms 158444 KB Output is correct
3 Correct 3581 ms 196512 KB Output is correct
4 Correct 994 ms 105160 KB Output is correct
5 Correct 4593 ms 253832 KB Output is correct
6 Correct 3701 ms 197136 KB Output is correct
7 Correct 1230 ms 42092 KB Output is correct
8 Correct 511 ms 30556 KB Output is correct
9 Correct 1345 ms 51768 KB Output is correct
10 Correct 1206 ms 43372 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 876 KB Output is correct
2 Correct 361 ms 9836 KB Output is correct
3 Correct 390 ms 9964 KB Output is correct
4 Correct 402 ms 10220 KB Output is correct
5 Correct 414 ms 10732 KB Output is correct
6 Correct 272 ms 9708 KB Output is correct
7 Correct 423 ms 10268 KB Output is correct
8 Correct 399 ms 10268 KB Output is correct
9 Correct 418 ms 10604 KB Output is correct
10 Correct 276 ms 9580 KB Output is correct
11 Correct 415 ms 10348 KB Output is correct
12 Correct 3 ms 620 KB Output is correct
13 Correct 2516 ms 158444 KB Output is correct
14 Correct 3581 ms 196512 KB Output is correct
15 Correct 994 ms 105160 KB Output is correct
16 Correct 4593 ms 253832 KB Output is correct
17 Correct 3701 ms 197136 KB Output is correct
18 Correct 1230 ms 42092 KB Output is correct
19 Correct 511 ms 30556 KB Output is correct
20 Correct 1345 ms 51768 KB Output is correct
21 Correct 1206 ms 43372 KB Output is correct
22 Correct 2946 ms 159172 KB Output is correct
23 Correct 2974 ms 162464 KB Output is correct
24 Correct 4046 ms 197868 KB Output is correct
25 Correct 4156 ms 201768 KB Output is correct
26 Correct 4196 ms 198476 KB Output is correct
27 Correct 5141 ms 251992 KB Output is correct
28 Correct 1222 ms 109140 KB Output is correct
29 Correct 4175 ms 198144 KB Output is correct
30 Correct 4192 ms 197356 KB Output is correct
31 Correct 4149 ms 198000 KB Output is correct
32 Correct 1390 ms 52508 KB Output is correct
33 Correct 529 ms 30856 KB Output is correct
34 Correct 947 ms 37100 KB Output is correct
35 Correct 972 ms 37832 KB Output is correct
36 Correct 1194 ms 40556 KB Output is correct
37 Correct 1147 ms 40812 KB Output is correct