oj.uz

Submission #384307

# Submission time Handle Problem Language Result Execution time Memory
384307 2021-04-01T09:51:17 Z shivensinha4 Factories (JOI14_factories) C++17
100 / 100
 5029 ms 253700 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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

Compilation message

factories.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
factories.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 748 KB Output is correct
2 Correct 359 ms 9580 KB Output is correct
3 Correct 391 ms 9836 KB Output is correct
4 Correct 386 ms 9836 KB Output is correct
5 Correct 412 ms 10348 KB Output is correct
6 Correct 278 ms 9324 KB Output is correct
7 Correct 391 ms 9964 KB Output is correct
8 Correct 428 ms 9952 KB Output is correct
9 Correct 416 ms 10220 KB Output is correct
10 Correct 267 ms 9452 KB Output is correct
11 Correct 393 ms 9836 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 2510 ms 158440 KB Output is correct
3 Correct 3489 ms 196204 KB Output is correct
4 Correct 959 ms 105160 KB Output is correct
5 Correct 4457 ms 253700 KB Output is correct
6 Correct 3650 ms 197100 KB Output is correct
7 Correct 1265 ms 41836 KB Output is correct
8 Correct 532 ms 30556 KB Output is correct
9 Correct 1384 ms 51392 KB Output is correct
10 Correct 1219 ms 43024 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 748 KB Output is correct
2 Correct 359 ms 9580 KB Output is correct
3 Correct 391 ms 9836 KB Output is correct
4 Correct 386 ms 9836 KB Output is correct
5 Correct 412 ms 10348 KB Output is correct
6 Correct 278 ms 9324 KB Output is correct
7 Correct 391 ms 9964 KB Output is correct
8 Correct 428 ms 9952 KB Output is correct
9 Correct 416 ms 10220 KB Output is correct
10 Correct 267 ms 9452 KB Output is correct
11 Correct 393 ms 9836 KB Output is correct
12 Correct 3 ms 620 KB Output is correct
13 Correct 2510 ms 158440 KB Output is correct
14 Correct 3489 ms 196204 KB Output is correct
15 Correct 959 ms 105160 KB Output is correct
16 Correct 4457 ms 253700 KB Output is correct
17 Correct 3650 ms 197100 KB Output is correct
18 Correct 1265 ms 41836 KB Output is correct
19 Correct 532 ms 30556 KB Output is correct
20 Correct 1384 ms 51392 KB Output is correct
21 Correct 1219 ms 43024 KB Output is correct
22 Correct 2870 ms 159072 KB Output is correct
23 Correct 2984 ms 162284 KB Output is correct
24 Correct 4183 ms 197876 KB Output is correct
25 Correct 4256 ms 201644 KB Output is correct
26 Correct 4167 ms 198320 KB Output is correct
27 Correct 5029 ms 251784 KB Output is correct
28 Correct 1210 ms 109000 KB Output is correct
29 Correct 4164 ms 198036 KB Output is correct
30 Correct 4157 ms 197228 KB Output is correct
31 Correct 4287 ms 197940 KB Output is correct
32 Correct 1406 ms 52280 KB Output is correct
33 Correct 566 ms 30684 KB Output is correct
34 Correct 1008 ms 36972 KB Output is correct
35 Correct 1016 ms 37356 KB Output is correct
36 Correct 1281 ms 40384 KB Output is correct
37 Correct 1191 ms 40428 KB Output is correct