Submission #399887

#	Time	Username	Problem	Language	Result	Execution time	Memory
399887		nikatamliani	Factories (JOI14_factories)	C++14	100 / 100	4402 ms	199936 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 5e5+10, LOG = 20, oo = 1e18;
int sub[N], p[N], d[N];
ll dst[N][LOG], bst[N];
ll n, q;
bool vis[N];
vector<pair<int, ll>> edges[N];
void find_dists(int x, int p, int depth, int ct) {
	for(pair<int, ll> to : edges[x]) {
		if(to.first != p && !vis[to.first]) {
			dst[to.first][depth] = dst[x][depth] + to.second;
			find_dists(to.first, x, depth, ct); 
		}
	}
}
void find_sizes(int x, int p) {
	sub[x] = 1;
	for(pair<int, ll> to : edges[x]) {
		if(to.first != p && !vis[to.first]) {
			find_sizes(to.first, x);
			sub[x] += sub[to.first];
		}
	}
}
int find_centroid(int x, int p, int all) {
	for(pair<int, ll> to : edges[x]) {
		if(to.first != p && !vis[to.first] && sub[to.first] > all/2) {
			return find_centroid(to.first, x, all);
		}
	}
	return x;
}
void dfs(int x, int parent, int depth) {
	find_sizes(x, -1);
	int c = find_centroid(x, -1, sub[x]);
	d[c] = depth;
	p[c] = parent;
	find_dists(c, -1, depth, c);
	vis[c] = 1;
	for(pair<int, ll> to : edges[c]) {
		if(!vis[to.first]) {
			dfs(to.first, c, depth+1);
		}
	}
}
void add_edge(int u, int v, int w) {
	edges[u].push_back({v, w});
	edges[v].push_back({u, w});
}
void mini(ll &x, ll y) {
	if(x > y) x = y; 
}
void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N-1; ++i) {
		add_edge(A[i], B[i], D[i]);
	}
	for(int i = 0; i < N; ++i) {
		bst[i] = oo;
	}
	dfs(0, -1, 0);
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<int> visited;
	ll ans = oo;
	for(int i = 0; i < S; ++i) {
		int x = X[i];
		int dt = d[x];
		int c = x;
		while(~c) {
			visited.push_back(c);
			mini(bst[c], dst[x][dt]);
			c = p[c];
			--dt;
		}
	}
	for(int i = 0; i < T; ++i) {
		int x = Y[i];
		int dt = d[x];
		int c = x;
		while(~c) {
			ans = min(ans, bst[c] + dst[x][dt]);
			c = p[c];
			--dt;
		}
	}
	for(int c : visited) bst[c] = oo;
	return ans;
}

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