Submission #411062

#	Time	Username	Problem	Language	Result	Execution time	Memory
411062		dynam1c	Factories (JOI14_factories)	C++17	33 / 100	8023 ms	313548 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;
vector<bool> vis;
vector<int> sz;
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];
}
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;
}
void Init(int nn, int aa[], int bb[], int d[]) {
	n = nn;
	graph.resize(n);
	ctree.resize(n);
	a.resize(n);
	b.resize(n);
	vis.resize(n);
	sz.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]);
	}
	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