Submission #363680

#	Time	Username	Problem	Language	Result	Execution time	Memory
363680		shivensinha4	Factories (JOI14_factories)	C++17	100 / 100	7385 ms	371396 KiB

factories

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

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67