oj.uz

Submission #52231

# Submission time Handle Problem Language Result Execution time Memory
52231 2018-06-25T05:38:13 Z gs14004 Factories (JOI14_factories) C++17
100 / 100
 3052 ms 145436 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 between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < to[p].size(); i++) {
                 ~~^~~~~~~~~~~~~~
factories.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < to[p].size(); i++)
                 ~~^~~~~~~~~~~~~~
factories.cpp: In function 'void init_lca()':
factories.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  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 between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cityX.size(); i++) {
                 ~~^~~~~~~~~~~~~~
factories.cpp:183:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cityY.size(); i++) {
                 ~~^~~~~~~~~~~~~~
factories.cpp:192:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < ord.size(); i++) {
                 ~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 57080 KB Output is correct
2 Correct 764 ms 65516 KB Output is correct
3 Correct 788 ms 65516 KB Output is correct
4 Correct 748 ms 65752 KB Output is correct
5 Correct 729 ms 65916 KB Output is correct
6 Correct 825 ms 66040 KB Output is correct
7 Correct 804 ms 66040 KB Output is correct
8 Correct 761 ms 66040 KB Output is correct
9 Correct 821 ms 66084 KB Output is correct
10 Correct 733 ms 66140 KB Output is correct
11 Correct 759 ms 66140 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 66140 KB Output is correct
2 Correct 2003 ms 122344 KB Output is correct
3 Correct 2013 ms 122620 KB Output is correct
4 Correct 1712 ms 125312 KB Output is correct
5 Correct 2309 ms 141940 KB Output is correct
6 Correct 1976 ms 141940 KB Output is correct
7 Correct 1276 ms 141940 KB Output is correct
8 Correct 1155 ms 141940 KB Output is correct
9 Correct 1134 ms 141940 KB Output is correct
10 Correct 1389 ms 141940 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 57080 KB Output is correct
2 Correct 764 ms 65516 KB Output is correct
3 Correct 788 ms 65516 KB Output is correct
4 Correct 748 ms 65752 KB Output is correct
5 Correct 729 ms 65916 KB Output is correct
6 Correct 825 ms 66040 KB Output is correct
7 Correct 804 ms 66040 KB Output is correct
8 Correct 761 ms 66040 KB Output is correct
9 Correct 821 ms 66084 KB Output is correct
10 Correct 733 ms 66140 KB Output is correct
11 Correct 759 ms 66140 KB Output is correct
12 Correct 51 ms 66140 KB Output is correct
13 Correct 2003 ms 122344 KB Output is correct
14 Correct 2013 ms 122620 KB Output is correct
15 Correct 1712 ms 125312 KB Output is correct
16 Correct 2309 ms 141940 KB Output is correct
17 Correct 1976 ms 141940 KB Output is correct
18 Correct 1276 ms 141940 KB Output is correct
19 Correct 1155 ms 141940 KB Output is correct
20 Correct 1134 ms 141940 KB Output is correct
21 Correct 1389 ms 141940 KB Output is correct
22 Correct 2351 ms 141940 KB Output is correct
23 Correct 2493 ms 141940 KB Output is correct
24 Correct 2366 ms 141940 KB Output is correct
25 Correct 2460 ms 141940 KB Output is correct
26 Correct 2631 ms 141940 KB Output is correct
27 Correct 2547 ms 145436 KB Output is correct
28 Correct 2233 ms 145436 KB Output is correct
29 Correct 2771 ms 145436 KB Output is correct
30 Correct 3052 ms 145436 KB Output is correct
31 Correct 2924 ms 145436 KB Output is correct
32 Correct 1279 ms 145436 KB Output is correct
33 Correct 1180 ms 145436 KB Output is correct
34 Correct 1204 ms 145436 KB Output is correct
35 Correct 1319 ms 145436 KB Output is correct
36 Correct 1366 ms 145436 KB Output is correct
37 Correct 1445 ms 145436 KB Output is correct