oj.uz

Submission #273506

# Submission time Handle Problem Language Result Execution time Memory
273506 2020-08-19T05:38:34 Z shivensinha4 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 334428 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);
	}
}

set<int> updated;

void update(int p) {
	int v = p;
	while (v != -1) {
		ll d = dist(p, v);
		whiteDist[v] = min(whiteDist[v], d);
		updated.insert(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 26 ms 1024 KB Output is correct
2 Correct 1609 ms 14452 KB Output is correct
3 Correct 1865 ms 14456 KB Output is correct
4 Correct 1806 ms 12840 KB Output is correct
5 Correct 2081 ms 12768 KB Output is correct
6 Correct 568 ms 11896 KB Output is correct
7 Correct 1839 ms 11360 KB Output is correct
8 Correct 1907 ms 10872 KB Output is correct
9 Correct 2415 ms 11312 KB Output is correct
10 Correct 610 ms 10772 KB Output is correct
11 Correct 1986 ms 11032 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 5587 ms 293352 KB Output is correct
3 Correct 6447 ms 300120 KB Output is correct
4 Correct 1982 ms 291908 KB Output is correct
5 Correct 7844 ms 334428 KB Output is correct
6 Correct 6748 ms 299344 KB Output is correct
7 Correct 6710 ms 64616 KB Output is correct
8 Correct 1556 ms 63492 KB Output is correct
9 Correct 7287 ms 69128 KB Output is correct
10 Correct 6369 ms 65204 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1024 KB Output is correct
2 Correct 1609 ms 14452 KB Output is correct
3 Correct 1865 ms 14456 KB Output is correct
4 Correct 1806 ms 12840 KB Output is correct
5 Correct 2081 ms 12768 KB Output is correct
6 Correct 568 ms 11896 KB Output is correct
7 Correct 1839 ms 11360 KB Output is correct
8 Correct 1907 ms 10872 KB Output is correct
9 Correct 2415 ms 11312 KB Output is correct
10 Correct 610 ms 10772 KB Output is correct
11 Correct 1986 ms 11032 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 5587 ms 293352 KB Output is correct
14 Correct 6447 ms 300120 KB Output is correct
15 Correct 1982 ms 291908 KB Output is correct
16 Correct 7844 ms 334428 KB Output is correct
17 Correct 6748 ms 299344 KB Output is correct
18 Correct 6710 ms 64616 KB Output is correct
19 Correct 1556 ms 63492 KB Output is correct
20 Correct 7287 ms 69128 KB Output is correct
21 Correct 6369 ms 65204 KB Output is correct
22 Execution timed out 8102 ms 296160 KB Time limit exceeded
23 Halted 0 ms 0 KB -