oj.uz

Submission #273478

# Submission time Handle Problem Language Result Execution time Memory
273478 2020-08-19T05:33:02 Z shivensinha4 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 336228 KB 
#include <bits/stdc++.h>
#include "factories.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'
 
class SparseTable {
	vector<vector<ii>> st;
	vector<ll> log; vector<ii> raw;
	int n;
 
	void computeLog() {
		log.resize(n+1, -1);
		int p = 0, two_pow = 1;
		while (two_pow <= n) {
			log[two_pow] = p++;
			two_pow *= 2;
		}
		int prev = 0;
		for_(i, 1, n+1) {
			if (log[i] != -1) prev = log[i];
			else log[i] = prev;
		}
	}
 
	void buildTable() {
		int k = log[n]+1;
		st.resize(n, vector<ii> (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<ii> nums) {
		raw = nums;
		n = nums.size();
		computeLog();
		buildTable();
	}
 
	int mn(int l, int r) {
		int p = log[r-l+1];
		return min(st[l][p], st[r - (1<<p) + 1][p]).second;
	}
};
 
 
int n;
vector<vector<pair<int, ll>>> adjList;
vi removed, subtreeSize, centroid, tin, depth;
vector<ll> rootDist, whiteDist;
vector<ii> tour;
SparseTable st;
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.first != parent) {
		rootDist[i.first] = rootDist[p]+i.second;
		depth[i.first] = depth[p]+1;
		s += dfs(i.first, 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.first] and subtreeSize[i.first] > sizeLimit) {
		invalidChild = i.first;
		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.first]) {
		centroid[i.first] = p;
		decompose(i.first, p);
	}
}

vi updated;

void update(int p) {
	int v = p;
	while (v != -1) {
		ll d = dist(p, v);
		whiteDist[v] = min(whiteDist[v], d);
		updated.push_back(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);
	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[]) {
	updated.clear();
	
	for_(i, 0, S) update(X[i]);
	ll val = INF;
	for_(i, 0, T) val = min(val, ans(Y[i]));
	for (int i: updated) whiteDist[i] = INF;
	
	return val;
}
 
//int main() {
	//#ifndef ONLINE_JUDGE
	//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;
//}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1024 KB Output is correct
2 Correct 681 ms 11512 KB Output is correct
3 Correct 870 ms 11808 KB Output is correct
4 Correct 1004 ms 11696 KB Output is correct
5 Correct 985 ms 12048 KB Output is correct
6 Correct 433 ms 11384 KB Output is correct
7 Correct 964 ms 11668 KB Output is correct
8 Correct 1054 ms 11640 KB Output is correct
9 Correct 944 ms 12044 KB Output is correct
10 Correct 497 ms 11512 KB Output is correct
11 Correct 885 ms 11512 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 4050 ms 293632 KB Output is correct
3 Correct 4547 ms 308516 KB Output is correct
4 Correct 2205 ms 294980 KB Output is correct
5 Correct 5825 ms 336228 KB Output is correct
6 Correct 4595 ms 301152 KB Output is correct
7 Correct 4184 ms 78056 KB Output is correct
8 Correct 1232 ms 77100 KB Output is correct
9 Correct 5441 ms 82844 KB Output is correct
10 Correct 3875 ms 78944 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1024 KB Output is correct
2 Correct 681 ms 11512 KB Output is correct
3 Correct 870 ms 11808 KB Output is correct
4 Correct 1004 ms 11696 KB Output is correct
5 Correct 985 ms 12048 KB Output is correct
6 Correct 433 ms 11384 KB Output is correct
7 Correct 964 ms 11668 KB Output is correct
8 Correct 1054 ms 11640 KB Output is correct
9 Correct 944 ms 12044 KB Output is correct
10 Correct 497 ms 11512 KB Output is correct
11 Correct 885 ms 11512 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 4050 ms 293632 KB Output is correct
14 Correct 4547 ms 308516 KB Output is correct
15 Correct 2205 ms 294980 KB Output is correct
16 Correct 5825 ms 336228 KB Output is correct
17 Correct 4595 ms 301152 KB Output is correct
18 Correct 4184 ms 78056 KB Output is correct
19 Correct 1232 ms 77100 KB Output is correct
20 Correct 5441 ms 82844 KB Output is correct
21 Correct 3875 ms 78944 KB Output is correct
22 Correct 5841 ms 298328 KB Output is correct
23 Correct 6266 ms 301260 KB Output is correct
24 Correct 7405 ms 303208 KB Output is correct
25 Correct 7345 ms 306568 KB Output is correct
26 Correct 7067 ms 303916 KB Output is correct
27 Execution timed out 8076 ms 331740 KB Time limit exceeded
28 Halted 0 ms 0 KB -