Submission #25297

# Submission time Handle Problem Language Result Execution time Memory
25297 2017-06-21T06:04:00 Z dotorya Factories (JOI14_factories) C++14
Compilation error
0 ms 0 KB
#include <algorithm>
#include <stdlib.h> 
#include <vector>
#include "factories.h"

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

bool dchk[500050];
int dep[500050];
int lr[500050][2];
ll par[500050][20][2];
int tus;
vector <pll> conn[500050];
void DFS(int n) {
	dchk[n] = true;
	lr[n][0] = ++tus;
	for (auto it : conn[n]) {
		if (dchk[it.second]) continue;
		par[it.second][0][0] = n, par[it.second][0][1] = it.first;
		for (int i = 1; i <= 18; i++) {
			int tp = par[it.second][i - 1][0];
			par[it.second][i][0] = par[tp][i - 1][0];
			par[it.second][i][1] = par[it.second][i - 1][1] + par[tp][i - 1][1];
		}
		dep[it.second] = dep[n] + 1;
		DFS(it.second);
	}
	lr[n][1] = tus;
}
pll lca(int a, int b) {
	ll rv = 0;
	if (dep[a] > dep[b]) swap(a, b);
	int c = dep[b] - dep[a];
	for (int i = 18; i >= 0; i--) {
		if (c & (1 << i)) {
			rv += par[b][i][1];
			b = par[b][i][0];
		}
	}
	if (a == b) return pll(rv, a);

	for (int i = 18; i >= 0; i--) {
		if (par[a][i][0] != par[b][i][0]) {
			rv += par[a][i][1];
			rv += par[b][i][1];
			a = par[a][i][0];
			b = par[b][i][0];
		}
	}
	rv += par[a][0][1];
	rv += par[b][0][1];
	return pll(rv, par[a][0][0]);
}
void Init(int N, int A[], int B[], int D[]) {
	int i, j;
	for (i = 0; i <= N - 2; i++) {
		conn[A[i]].emplace_back(D[i], B[i]);
		conn[B[i]].emplace_back(D[i], A[i]);
	}

	tus = 0;
	DFS(0);
}

class Node {
public:
	ll mn, v;
	Node() {
		*this = Node(0, 0);
	}
	Node(ll mn, ll v) : mn(mn), v(v) {}
};
Node indt[1100000];
void update(int st, int en, int S, int E, int n, ll v) {
	if (st > en) return;
	if (st == S && en == E) {
		indt[n].mn += v;
		indt[n].v += v;
		return;
	}

	int M = (S + E) / 2;
	update(st, min(en, M), S, M, 2 * n, v);
	update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
	indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn) + indt[n].v;
}

ll qans;
vector <int> Vv;
vector <int> Vv2;
vector <pll> conn2[500050];
vector <pll> son2[500050];
ll dis[500050];
int lr2[500050][2];
int tchk[500050];
void DFS2(int n) {
	dchk[n] = true;
	lr2[n][0] = ++tus;
	for (auto it : conn2[n]) {
		if (dchk[it.second]) continue;
		son2[n].push_back(it);
		dis[it.second] = dis[n] + it.first;
		DFS2(it.second);
	}
	lr2[n][1] = tus;
}
void DFS3(int n) {
	if (tchk[n] == 1) qans = min(qans, indt[1].mn);
	for (auto it : son2[n]) {
		indt[1].mn += it.first, indt[1].v += it.first;
		update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, -2 * it.first);
		DFS3(it.second);
		indt[1].mn -= it.first, indt[1].v -= it.first;
		update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, 2 * it.first);
	}
}
long long Query(int S, int X[], int T, int Y[]) {
	Vv.reserve(2 * (S + T));
	Vv2.reserve(S + T);
	int i, j;
	for (i = 0; i < S; i++) Vv.push_back(X[i]);
	for (i = 0; i < T; i++) Vv.push_back(Y[i]);
	sort(all(Vv), [](int a, int b) {
		return lr[a][0] < lr[b][0];
	});

	for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
	for (auto it : Vv2) Vv.push_back(it);
	sort(all(Vv), [](int a, int b) {
		return lr[a][0] < lr[b][0];
	});
	Vv.erase(unique(all(Vv)), Vv.end());
	for (auto it : Vv) tchk[it] = 0;
	for (i = 0; i < S; i++) tchk[X[i]] = 1;
	for (i = 0; i < T; i++) tchk[Y[i]] = -1;

	for (i = 0; i + 1 < Vv.size(); i++) {
		int x = Vv[i];
		int y = Vv[i + 1];
		x = lca(x, y).second;
		pll u = lca(x, y);
		conn2[x].emplace_back(u.first, y);
		conn2[y].emplace_back(u.first, x);
	}

	for (i = 0; i < Vv.size(); i++) {
		dchk[Vv[i]] = false;
		dis[Vv[i]] = 0;
	}
	tus = 0;
	DFS2(Vv[0]);
	for (IT_MAX = 2; IT_MAX < Vv.size(); IT_MAX *= 2);
	for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node(0, 0);
	for (i = 0; i < Vv.size(); i++) {
		ll v = dis[Vv[i]];
		if (tchk[Vv[i]] != -1) v = LL_INF;

		update(lr2[Vv[i]][0], lr2[Vv[i]][0], 1, IT_MAX, 1, v);
	}
	update(Vv.size() + 1, IT_MAX, 1, IT_MAX, 1, LL_INF);
	qans = LL_INF;
	DFS3(Vv[0]);

	for (auto it : Vv) {
		conn2[it].clear();
		son2[it].clear();
	}
	Vv.clear();
	Vv2.clear();
	return qans;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:59:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
factories.cpp: In function 'void DFS3(int)':
factories.cpp:115:51: error: 'IT_MAX' was not declared in this scope
   update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, -2 * it.first);
                                                   ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:127:13: error: 'all' was not declared in this scope
  sort(all(Vv), [](int a, int b) {
             ^
factories.cpp:131:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
                    ^
factories.cpp:141:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i + 1 < Vv.size(); i++) {
                    ^
factories.cpp:150:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Vv.size(); i++) {
                ^
factories.cpp:156:7: error: 'IT_MAX' was not declared in this scope
  for (IT_MAX = 2; IT_MAX < Vv.size(); IT_MAX *= 2);
       ^
factories.cpp:157:22: error: 'IT_MAX' was not declared in this scope
  for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node(0, 0);
                      ^
factories.cpp:158:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Vv.size(); i++) {
                ^
factories.cpp:162:43: error: 'IT_MAX' was not declared in this scope
   update(lr2[Vv[i]][0], lr2[Vv[i]][0], 1, IT_MAX, 1, v);
                                           ^
factories.cpp:164:24: error: 'IT_MAX' was not declared in this scope
  update(Vv.size() + 1, IT_MAX, 1, IT_MAX, 1, LL_INF);
                        ^
factories.cpp:124:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^