Submission #1031800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031800		juicy	Factories (JOI14_factories)	C++17	100 / 100	2793 ms	184196 KiB

factories

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int mxN = 5e5 + 5, LG = 20;
const long long inf = 1e18;
 
int ord[mxN], sz[mxN], pr[mxN], spt[LG][2 * mxN];
long long dep[mxN], mn[mxN];
bool del[mxN];
vector<pair<int, int>> g[mxN];
 
int timer = 0;
 
void pre_dfs(int u) {
	spt[0][ord[u] = ++timer] = u;
	for (auto [v, w] : g[u]) {
		if (!ord[v]) {
			dep[v] = dep[u] + w;
			pre_dfs(v);
			spt[0][++timer] = u;
		}
	}
}
 
int mint(int u, int v) {
	return ord[u] < ord[v] ? u : v;
}
 
int lca(int u, int v) {
	int l = ord[u], r = ord[v];
	if (l > r) {
		swap(l, r);
	}
	int k = __lg(r - l + 1);
	return mint(spt[k][l], spt[k][r - (1 << k) + 1]);
}
 
long long dis(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
 
void dfs(int u, int p) {
	sz[u] = 1;
	for (auto [v, w] : g[u]) {
		if (!del[v] && v != p) {
			dfs(v, u);
			sz[u] += sz[v];
		}
	}
}
 
int findCen(int u, int p, int tot) {
	for (auto [v, w] : g[u]) {
		if (!del[v] && v != p && sz[v] * 2 > tot) {
			return findCen(v, u, tot);
		}
	}
	return u;
}
 
int split(int u) {
	dfs(u, u);
	u = findCen(u, u, sz[u]);
  	del[u] = 1;
	for (auto [v, w] : g[u]) {
		if (!del[v]) {
			pr[split(v)] = u;
		}
	}
  return u;
}
 
void ins(int u) {
	for (int p = u; p; p = pr[p]) {
		mn[p] = min(mn[p], dis(u, p));
	}
}
 
void ers(int u) {
	for (int p = u; p; p = pr[p]) {
		mn[p] = inf;
	}
}
 
long long get(int u) {
	long long ans = inf;
	for (int p = u; p; p = pr[p]) {
		ans = min(ans, mn[p] + dis(p, u));
	}
	return ans;
}
 
void Init(int N, int *A, int *B, int *D) {
	for (int i = 0; i < N - 1; ++i) {
    	++A[i], ++B[i];
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	pre_dfs(1);
	for (int j = 1; j < LG; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
			spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
		}
	}
	split(1);
	fill(mn + 1, mn + N + 1, inf);
}
 
long long Query(int S, int *X, int T, int *Y) {
	for (int i = 0; i < T; ++i) {
		ins(++Y[i]);
	}
	long long res = inf;
	for (int i = 0; i < S; ++i) {
		res = min(res, get(++X[i]));
	}
	for (int i = 0; i < T; ++i) {
		ers(Y[i]);
	}
	return res;
}

Compilation message (stderr)

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:109:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  109 |    spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                         ~~^~~

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