oj.uz

Submission #363682

# Submission time Handle Problem Language Result Execution time Memory
363682 2021-02-06T20:41:17 Z shivensinha4 Factories (JOI14_factories) C++17
100 / 100
 7016 ms 359752 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

class SparseTable {
	vector<vector<array<int, 2>>> st;
	vector<array<int, 2>> raw;
	int n;
	
	void buildTable() {
		int k = __lg(n)+1;
		st.resize(n, vector<array<int, 2>> (k));
		for_(i, 0, n) st[i][0] = raw[i];
		for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1)
				st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]);
	}

public:
	void build(vector<array<int, 2>> nums) {
		raw = nums;
		n = nums.size();
		buildTable();
	}
	
	int mn(int l, int r) {
		int p = __lg(r-l+1);
		return min(st[l][p], st[r - (1<<p) + 1][p])[1];
	}
};


int n;
vector<vector<array<ll, 2>>> adjList;
vi removed, subtreeSize, centroid, tin, depth;
vector<ll> rootDist, whiteDist;
vector<array<int, 2>> tour;
SparseTable st;
const ll INF = 1e15;

int dfs(int p, int parent) {
	int s = 1;
	tin[p] = tour.size();
	tour.push_back({depth[p], p});
	
	for (auto i: adjList[p]) if (i[0] != parent) {
			rootDist[i[0]] = rootDist[p]+i[1];
			depth[i[0]] = depth[p]+1;
			s += dfs(i[0], p);
			tour.push_back({depth[p], p});
		}
	
	subtreeSize[p] = s;
	return s;
}

int lca(int u, int v) {
	return st.mn(min(tin[u], tin[v]), max(tin[u], tin[v]));
}

ll dist(int u, int v) {
	int lc = lca(u, v);
	return rootDist[u] + rootDist[v] - 2*rootDist[lc];
}

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;
	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;
	while (v != -1) {
		ll d = dist(p, v);
		whiteDist[v] = min(whiteDist[v], d);
		updated[pt++] = v;
		v = centroid[v];
	}
}

ll ans(int p) {
	ll val = INF;
	int v = p;
	while (v != -1) {
		val = min(val, whiteDist[v] + dist(p, v));
		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); depth.resize(n); tin.resize(n); rootDist.resize(n); whiteDist.resize(n, INF); updated.resize(10*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);
	st.build(tour);
}

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;
}

//int main() {
//#ifdef mlocal
//	freopen("test.in", "r", stdin);
//#endif
//
//	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;
//}

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 26 ms 1004 KB Output is correct
2 Correct 662 ms 13372 KB Output is correct
3 Correct 869 ms 13316 KB Output is correct
4 Correct 813 ms 13292 KB Output is correct
5 Correct 867 ms 13804 KB Output is correct
6 Correct 364 ms 13232 KB Output is correct
7 Correct 827 ms 13420 KB Output is correct
8 Correct 837 ms 13420 KB Output is correct
9 Correct 834 ms 13804 KB Output is correct
10 Correct 355 ms 13164 KB Output is correct
11 Correct 818 ms 13304 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 620 KB Output is correct
2 Correct 3427 ms 305768 KB Output is correct
3 Correct 3628 ms 312904 KB Output is correct
4 Correct 1632 ms 303292 KB Output is correct
5 Correct 4734 ms 359752 KB Output is correct
6 Correct 3991 ms 312776 KB Output is correct
7 Correct 3030 ms 67932 KB Output is correct
8 Correct 968 ms 66568 KB Output is correct
9 Correct 3203 ms 73936 KB Output is correct
10 Correct 3110 ms 68672 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1004 KB Output is correct
2 Correct 662 ms 13372 KB Output is correct
3 Correct 869 ms 13316 KB Output is correct
4 Correct 813 ms 13292 KB Output is correct
5 Correct 867 ms 13804 KB Output is correct
6 Correct 364 ms 13232 KB Output is correct
7 Correct 827 ms 13420 KB Output is correct
8 Correct 837 ms 13420 KB Output is correct
9 Correct 834 ms 13804 KB Output is correct
10 Correct 355 ms 13164 KB Output is correct
11 Correct 818 ms 13304 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 3427 ms 305768 KB Output is correct
14 Correct 3628 ms 312904 KB Output is correct
15 Correct 1632 ms 303292 KB Output is correct
16 Correct 4734 ms 359752 KB Output is correct
17 Correct 3991 ms 312776 KB Output is correct
18 Correct 3030 ms 67932 KB Output is correct
19 Correct 968 ms 66568 KB Output is correct
20 Correct 3203 ms 73936 KB Output is correct
21 Correct 3110 ms 68672 KB Output is correct
22 Correct 4895 ms 308296 KB Output is correct
23 Correct 5227 ms 308940 KB Output is correct
24 Correct 6086 ms 314320 KB Output is correct
25 Correct 5996 ms 316656 KB Output is correct
26 Correct 5988 ms 315208 KB Output is correct
27 Correct 7016 ms 351816 KB Output is correct
28 Correct 2084 ms 306748 KB Output is correct
29 Correct 6036 ms 314884 KB Output is correct
30 Correct 6271 ms 313416 KB Output is correct
31 Correct 6153 ms 314648 KB Output is correct
32 Correct 3556 ms 74752 KB Output is correct
33 Correct 1006 ms 66368 KB Output is correct
34 Correct 2751 ms 65632 KB Output is correct
35 Correct 2817 ms 65376 KB Output is correct
36 Correct 3302 ms 66780 KB Output is correct
37 Correct 3313 ms 66460 KB Output is correct