Submission #411060

#	Time	Username	Problem	Language	Result	Execution time	Memory
411060		dynam1c	Factories (JOI14_factories)	C++17	33 / 100	8064 ms	322116 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(x) x.begin(), x.end()

vector<vector<pair<int, ll>>> graph;
vector<vector<int>> ctree;
int croot;
vector<vector<ll>> depth, subtree; // [level][v]
constexpr int L = 20;
int n;
vector<vector<int>> a, b;
void Init(int nn, int aa[], int bb[], int d[]) {
	n = nn;
	graph.resize(n);
	ctree.resize(n);
	a.resize(n);
	b.resize(n);
	depth.assign(L, vector<ll>(n));
	subtree.assign(L, vector<ll>(n));
	for (int i = 0; i < n-1; i++) {
		graph[aa[i]].emplace_back(bb[i], d[i]);
		graph[bb[i]].emplace_back(aa[i], d[i]);
	}
	vector<bool> vis(n);
	vector<int> sz(n);
	function<int(int, int, int, int)> calc = [&](int v, int p, int l, int c) {
		if (v == p and l >= 0)
			depth[l][v] = 0;
		if (l > 0)
			subtree[l-1][v] = c;
		sz[v] = 1;
		for (auto [ne, w] : graph[v])
			if (!vis[ne] and ne != p) {
				if (l >= 0)
					depth[l][ne] = depth[l][v]+w;
				sz[v] += calc(ne, v, l, c);
			}
		return sz[v];
	};
	function<int(int, int)> centroid = [&](int v, int l) {
		int k = calc(v, v, -1, 0), c = v;
		bool cont = true;
		while (cont) {
			cont = false;
			for (auto [ne, w] : graph[c]) if (!vis[ne] and sz[ne] < sz[c] and 2*sz[ne] > k)
				cont = true, c = ne;
		}
		calc(c, c, l, c);
		vis[c] = true;
		for (auto [ne, w] : graph[c]) {
			if (!vis[ne])
				ctree[c].push_back(centroid(ne, l+1));
		}
		return c;
	};
	croot = centroid(0, 0);
}

ll qq(int v, int l) {
	if (a[v].empty() or b[v].empty()) {
		a[v].clear(), b[v].clear();
		return LLONG_MAX;
	}
	ll ax = LLONG_MAX, bx = LLONG_MAX;
	vector<int> nxt;
	for (int e : a[v]) {
		ax = min(ax, depth[l][e]);
		if (e != v) 
			a[subtree[l][e]].push_back(e), nxt.push_back(subtree[l][e]);
	}
	for (int e : b[v]) {
		bx = min(bx, depth[l][e]);
		if (e != v)
			b[subtree[l][e]].push_back(e), nxt.push_back(subtree[l][e]);
	}
	/*cout << v << endl;
	for (int e : a[v])
		cout << " " << e;
	cout << endl;
	for (int e : b[v])
		cout << " " << e;
	cout << endl;*/
	ll res = ax+bx;
	for (int ne : nxt)
		res = min(res, qq(ne, l+1));
	a[v].clear(), b[v].clear();
	return res;
}

long long Query(int s, int x[], int t, int y[]) {
	for (int i = 0; i < s; i++)
		a[croot].push_back(x[i]);
	for (int i = 0; i < t; i++)
		b[croot].push_back(y[i]);
	return qq(croot, 0);
}

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