Submission #869469

#	Time	Username	Problem	Language	Result	Execution time	Memory
869469		SUNWOOOOOOOO	Factories (JOI14_factories)	C++17	100 / 100	1338 ms	183956 KiB

factories

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

typedef long long i64;

const int MAXN = 500500;
const i64 INF = 1LL << 60LL;

template <class T>
struct RMQ
{
	static const int DEPTH = 20;
	static const int N = 1 << DEPTH;

	T val[2 * N];
	T TINF;

	RMQ(T TINF_) { TINF = TINF_; }

	void init()
	{
		for(int i = 0; i < 2 * N; i++) val[i] = TINF;
	}

	void init(T* iv, int sz)
	{
		for(int i = 0; i < sz; i++) val[i + N] = iv[i];
		for(int i = sz; i < N; i++) val[i + N] = TINF;

		for(int i = N-1; i >= 1; i--) val[i] = min(val[i*2], val[i*2+1]);
	}

	void init(vector<T> &iv)
	{
		int sz = iv.size();
		for(int i = 0; i < sz; i++) val[i + N] = iv[i];

		int L = N, R = N + sz;
		L >>= 1; R >>= 1;

		while(L < R) {
			for(int i = L; i < R; i++) val[i] = min(val[i*2], val[i*2+1]);
			L >>= 1; R >>= 1;
		}
	}

	void set_value(int p, T v)
	{
		p += N;
		val[p] = v;
		p >>= 1;

		while(p) {
			val[p] = min(val[p*2], val[p*2+1]);
			p >>= 1;
		}
	}

	T query(int L, int R)
	{
		T ret = TINF;
		L += N; R += N;
		while(L < R) {
			if(L & 1) ret = min(ret, val[L++]);
			if(R & 1) ret = min(ret, val[--R]);

			L >>= 1; R >>= 1;
		}
		return ret;
	}
};

int N, M, Q;
vector<int> to[MAXN], dist[MAXN];

int root[MAXN], lv[MAXN], ll;
i64 depth[MAXN];
vector<int> el;

RMQ <pair<int, int> > lca_tbl (make_pair(INT_MAX, 0));
pair<int, int> lca_sub[2*MAXN];
bool city_kind[MAXN];

void euler_tour(int p, int rt, i64 cd)
{
	depth[p] = cd;
	root[p] = rt;
	lv[p] = el.size();

	el.push_back(p);

	for(int i = 0; i < to[p].size(); i++) {
		if(to[p][i] == rt) continue;

		euler_tour(to[p][i], p, cd + dist[p][i]);

		el.push_back(p);
	}

	for(int i = 0; i < to[p].size(); i++)
		if(to[p][i] == root[p]) {
			to[p].erase(to[p].begin() + i);
			dist[p].erase(dist[p].begin() + i);
		}
}

void init_lca()
{
	for(int i = 0; i < el.size(); i++) {
		lca_sub[i] = make_pair(lv[el[i]], el[i]);
	}

	lca_tbl.init(lca_sub, el.size());
}

int lca(int p, int q)
{
	if(lv[p] > lv[q]) swap(p, q);

	return lca_tbl.query(lv[p], lv[q] + 1).second;
}

i64 sol;
vector<pair<int, int> > ord, ord2;
RMQ <pair<int, int> > rmq (make_pair(INT_MAX, INT_MAX));
vector<int> cityX, cityY;

pair<i64, i64> solve_small_dfs(int p, int q, int rt)
{
	if(p+1 == q) {
		i64 dd = (rt == -1 ? 0 : (depth[ord[p].second] - depth[rt]));

		if(city_kind[ord[p].second]) return make_pair(dd, INF);
		else return make_pair(INF, dd);
	}

	int bas = (int) rmq.query(p, q-1).second;

	pair<i64, i64> lf = solve_small_dfs(p, bas+1, ord2[bas].second),
				   rg = solve_small_dfs(bas+1, q, ord2[bas].second);
	i64 dd = (rt == -1 ? 0 : (depth[ord2[bas].second] - depth[rt]));

	sol = min(sol, min(lf.first + rg.second, lf.second + rg.first));
	return make_pair(dd + min(lf.first, rg.first), dd + min(lf.second, rg.second));
}

void Init(int N_, int A[], int B[], int D[])
{
	N = N_;

	for(int i = 0; i < N-1; i++) {
		to[A[i]].push_back(B[i]);
		dist[A[i]].push_back(D[i]);
		to[B[i]].push_back(A[i]);
		dist[B[i]].push_back(D[i]);
	}

	ll = 0;
	euler_tour(0, -1, 0);

	init_lca();
}

long long Query(int S, int X[], int T, int Y[])
{
	cityX.clear();
	for(int i = 0; i < S; i++) cityX.push_back(X[i]);
	cityY.clear();
	for(int i = 0; i < T; i++) cityY.push_back(Y[i]);

	ord.clear(); ord2.clear();

	for(int i = 0; i < cityX.size(); i++) {
		ord.push_back(make_pair(lv[cityX[i]], cityX[i]));
		city_kind[cityX[i]] = true;
	}

	for(int i = 0; i < cityY.size(); i++) {
		ord.push_back(make_pair(lv[cityY[i]], cityY[i]));
		city_kind[cityY[i]] = false;
	}

	sort(ord.begin(), ord.end());

	vector<pair<int, int> > ord3;

	for(int i = 1; i < ord.size(); i++) {
		int l = lca(ord[i-1].second, ord[i].second);

		ord2.push_back(make_pair(lv[l], l));
		ord3.push_back(make_pair(lv[l], i-1));
	}

	rmq.init(ord3);

	sol = INF;
	solve_small_dfs(0, ord.size(), -1);

	return sol;
}

Compilation message (stderr)

factories.cpp: In function 'void euler_tour(int, int, i64)':
factories.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int i = 0; i < to[p].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
factories.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i = 0; i < to[p].size(); i++)
      |                 ~~^~~~~~~~~~~~~~
factories.cpp: In function 'void init_lca()':
factories.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for(int i = 0; i < el.size(); i++) {
      |                 ~~^~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:178:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |  for(int i = 0; i < cityX.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
factories.cpp:183:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |  for(int i = 0; i < cityY.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
factories.cpp:192:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |  for(int i = 1; i < ord.size(); i++) {
      |                 ~~^~~~~~~~~~~~

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