oj.uz

Submission #6984

# Submission time Handle Problem Language Result Execution time Memory
6984 2014-07-12T06:50:50 Z model_code Factories (JOI14_factories) C++
100 / 100
 2444 ms 152828 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;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 95844 KB Output is correct
2 Correct 720 ms 96296 KB Output is correct
3 Correct 780 ms 96288 KB Output is correct
4 Correct 752 ms 96432 KB Output is correct
5 Correct 732 ms 96492 KB Output is correct
6 Correct 776 ms 96640 KB Output is correct
7 Correct 800 ms 96288 KB Output is correct
8 Correct 792 ms 96448 KB Output is correct
9 Correct 776 ms 96484 KB Output is correct
10 Correct 780 ms 96644 KB Output is correct
11 Correct 816 ms 96288 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 95844 KB Output is correct
2 Correct 1704 ms 134340 KB Output is correct
3 Correct 1716 ms 136080 KB Output is correct
4 Correct 1324 ms 137344 KB Output is correct
5 Correct 1760 ms 151204 KB Output is correct
6 Correct 1820 ms 135760 KB Output is correct
7 Correct 1316 ms 104060 KB Output is correct
8 Correct 1124 ms 104664 KB Output is correct
9 Correct 1156 ms 105756 KB Output is correct
10 Correct 1308 ms 103988 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2068 ms 137608 KB Output is correct
2 Correct 2212 ms 137024 KB Output is correct
3 Correct 2236 ms 139664 KB Output is correct
4 Correct 2288 ms 140284 KB Output is correct
5 Correct 2360 ms 135364 KB Output is correct
6 Correct 2312 ms 151544 KB Output is correct
7 Correct 1904 ms 152828 KB Output is correct
8 Correct 2424 ms 135392 KB Output is correct
9 Correct 2408 ms 135000 KB Output is correct
10 Correct 2444 ms 134880 KB Output is correct
11 Correct 1092 ms 113884 KB Output is correct
12 Correct 1140 ms 119824 KB Output is correct
13 Correct 1180 ms 103852 KB Output is correct
14 Correct 1172 ms 103856 KB Output is correct
15 Correct 1260 ms 103996 KB Output is correct
16 Correct 1344 ms 103984 KB Output is correct