Submission #25350

#	Time	Username	Problem	Language	Result	Execution time	Memory
25350		kdh9949	Factories (JOI14_factories)	C++14	0 / 100	5283 ms	107644 KiB

factories

#include "factories.h"
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

struct E{
	int x; ll d;
	bool operator<(const E &oth) const {
		return d > oth.d;
	}
};

const ll inf = 1e18;
int n, c[500010], r[500010], d[500010], sp[19][500010];
ll dd[500010], ans;
vector<E> e[500010];

void dfs(int x, int p, int de, ll dde){
	sp[0][x] = p;
	d[x] = de;
	dd[x] = dde;
	for(int i = 1; i < 19; i++) sp[i][x] = sp[i - 1][sp[i - 1][x]];
	for(auto &i : e[x]){
		if(i.x != p) dfs(i.x, x, de + 1, dde + i.d);
	}
}

ll dis(int x, int y){
	ll ret = dd[x] + dd[y];
	if(d[x] < d[y]) swap(x, y);
	for(int i = 18; i >= 0; i--){
		if(d[sp[i][x]] >= d[y]) x = sp[i][x];
	}
	if(x == y) return ret - 2 * dd[x];
	for(int i = 18; i >= 0; i--){
		if(sp[i][x] && sp[i][y] && sp[i][x] != sp[i][y]){
			x = sp[i][x];
			y = sp[i][y];
		}
	}
	return ret - 2 * dd[sp[0][x]];
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0, x, y, z; i < n - 1; i++){
		x = A[i] + 1; y = B[i] + 1; z = D[i];
		e[x].push_back({y, z});
		e[y].push_back({x, z});
	}
	dfs(1, 0, 1, 0);
}

ll h(int x, int p){
	ll ret = (c[x] ? 0 : inf);
	for(auto &i : e[x]){
		if(i.x != p) ret = min(ret, h(i.x, x) + i.d);
	}
	if(r[x]) ans = min(ans, ret);
	return ret;
}

ll f(int x, int a[], int y, int b[]){
	for(int i = 0; i < x; i++) c[a[i] + 1] = 1;
	for(int i = 0; i < y; i++) r[b[i] + 1] = 1;
	ans = inf;
	h(1, 0);
	for(int i = 0; i < x; i++) c[a[i] + 1] = 0;
	for(int i = 0; i < y; i++) r[b[i] + 1] = 0;
	return ans;
}

ll g(int x, int a[], int y, int b[]){
	ll ret = inf;
	for(int i = 0; i < x; i++){
		for(int j = 0; j < y; j++){
			ret = min(ret, dis(a[i] + 1, b[j] + 1));
		}
	}
	return ret;
}

ll Query(int S, int X[], int T, int Y[]) {
	if(19LL * S * T > n + S + T) return f(S, X, T, Y);
	return g(S, X, T, Y);
}

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