Submission #222029

#	Time	Username	Problem	Language	Result	Execution time	Memory
222029		Dan13llljws	Factories (JOI14_factories)	C++14	100 / 100	4993 ms	176064 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<int, int> pii;
#define ms(x, y) memset(x, y, sizeof(x))
#define pb push_back
#define f first
#define s second
const int mod = 1e9 + 7, base = 131, MM = 5e5 + 5, LG = 25;
int n, dep[MM], w[MM], pre[MM]; bool vis[MM];
ll dist[LG][MM], ans[MM];
vector<pii> adj[MM]; vector<int> clr;
void get_weight(int src, int par){
	w[src] = 1;
	for (auto v : adj[src]){
		if (v.s == par || vis[v.s]) continue;
		get_weight(v.s, src);
		w[src] += w[v.s];
	}
}
int get_cent(int src, int par, int wt){
	for (auto v : adj[src])
		if (v.s != par && !vis[v.s] && w[v.s] * 2 > wt)
			return get_cent(v.s, src, wt);
	return src;
}
void dfs(int src, int par, ll d, int lvl){
	dist[lvl][src] = d;
	for (auto v : adj[src]){
		if (v.s == par || vis[v.s]) continue;
		dfs(v.s, src, d + v.f, lvl);
	}
}
void decomp(int src, int lvl){
	dfs(src, src, 0, lvl);
	vis[src] = 1;
	for (auto v : adj[src]){
		if (vis[v.s]) continue;
		get_weight(v.s, src);
		int rt = get_cent(v.s, src, w[v.s]);
		pre[rt] = src, dep[rt] = lvl + 1;
		decomp(rt, lvl + 1);
	}
}
void Init(int N, int A[], int B[], int D[]){
	n = N;
	for (int i = 0; i < N - 1; i++){
		A[i]++, B[i]++;
		adj[A[i]].pb({D[i], B[i]});
		adj[B[i]].pb({D[i], A[i]});
	}	
	get_weight(1, 1);
	decomp(get_cent(1, 1, N), 0);
	ms(ans, INF);
}
long long Query(int S, int X[], int T, int Y[]){
	for (int i = 0; i < S; i++)
		for (int src = X[i] + 1, l = dep[src], tmp = src; l >= 0; l--, tmp = pre[tmp]){
			if (ans[tmp] == LLINF) clr.pb(tmp);
			ans[tmp] = min(ans[tmp], dist[l][src]);
		}
	ll ret = LLINF;
	for (int i = 0; i < T; i++)
		for (int src = Y[i] + 1, l = dep[src], tmp = src; l >= 0; l--, tmp = pre[tmp])
			ret = min(ret, dist[l][src] + ans[tmp]);
	for (int p : clr) ans[p] = LLINF;
	clr.clear();
	return ret;
}

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