oj.uz

Submission #869469

# Submission time Handle Problem Language Result Execution time Memory
869469 2023-11-04T12:02:37 Z SUNWOOOOOOOO Factories (JOI14_factories) C++17
100 / 100
 1338 ms 183956 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 83540 KB Output is correct
2 Correct 435 ms 94996 KB Output is correct
3 Correct 464 ms 94588 KB Output is correct
4 Correct 448 ms 95060 KB Output is correct
5 Correct 421 ms 94980 KB Output is correct
6 Correct 423 ms 94992 KB Output is correct
7 Correct 455 ms 94720 KB Output is correct
8 Correct 442 ms 94804 KB Output is correct
9 Correct 422 ms 95056 KB Output is correct
10 Correct 425 ms 94800 KB Output is correct
11 Correct 464 ms 94848 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 83548 KB Output is correct
2 Correct 952 ms 149148 KB Output is correct
3 Correct 906 ms 152004 KB Output is correct
4 Correct 724 ms 151696 KB Output is correct
5 Correct 956 ms 182184 KB Output is correct
6 Correct 964 ms 152492 KB Output is correct
7 Correct 640 ms 108848 KB Output is correct
8 Correct 563 ms 108992 KB Output is correct
9 Correct 576 ms 112580 KB Output is correct
10 Correct 638 ms 109112 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 83540 KB Output is correct
2 Correct 435 ms 94996 KB Output is correct
3 Correct 464 ms 94588 KB Output is correct
4 Correct 448 ms 95060 KB Output is correct
5 Correct 421 ms 94980 KB Output is correct
6 Correct 423 ms 94992 KB Output is correct
7 Correct 455 ms 94720 KB Output is correct
8 Correct 442 ms 94804 KB Output is correct
9 Correct 422 ms 95056 KB Output is correct
10 Correct 425 ms 94800 KB Output is correct
11 Correct 464 ms 94848 KB Output is correct
12 Correct 16 ms 83548 KB Output is correct
13 Correct 952 ms 149148 KB Output is correct
14 Correct 906 ms 152004 KB Output is correct
15 Correct 724 ms 151696 KB Output is correct
16 Correct 956 ms 182184 KB Output is correct
17 Correct 964 ms 152492 KB Output is correct
18 Correct 640 ms 108848 KB Output is correct
19 Correct 563 ms 108992 KB Output is correct
20 Correct 576 ms 112580 KB Output is correct
21 Correct 638 ms 109112 KB Output is correct
22 Correct 1114 ms 157236 KB Output is correct
23 Correct 1181 ms 158836 KB Output is correct
24 Correct 1198 ms 159932 KB Output is correct
25 Correct 1213 ms 162532 KB Output is correct
26 Correct 1279 ms 156092 KB Output is correct
27 Correct 1243 ms 183956 KB Output is correct
28 Correct 999 ms 168012 KB Output is correct
29 Correct 1309 ms 155540 KB Output is correct
30 Correct 1338 ms 155056 KB Output is correct
31 Correct 1329 ms 155988 KB Output is correct
32 Correct 576 ms 116576 KB Output is correct
33 Correct 562 ms 118012 KB Output is correct
34 Correct 579 ms 107324 KB Output is correct
35 Correct 572 ms 107204 KB Output is correct
36 Correct 633 ms 107840 KB Output is correct
37 Correct 645 ms 107752 KB Output is correct