oj.uz

Submission #25294

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

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:5:7: error: 'll' does not name a type
 const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
       ^
factories.cpp:9:1: error: 'll' does not name a type
 ll par[500050][20][2];
 ^
factories.cpp:11:1: error: 'vector' does not name a type
 vector <pll> conn[500050];
 ^
factories.cpp: In function 'void DFS(int)':
factories.cpp:15:17: error: 'conn' was not declared in this scope
  for (auto it : conn[n]) {
                 ^
factories.cpp:17:3: error: 'par' was not declared in this scope
   par[it.second][0][0] = n, par[it.second][0][1] = it.first;
   ^
factories.cpp: At global scope:
factories.cpp:28:1: error: 'pll' does not name a type
 pll lca(int a, int b) {
 ^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:55:3: error: 'conn' was not declared in this scope
   conn[A[i]].emplace_back(D[i], B[i]);
   ^
factories.cpp:53:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
factories.cpp: At global scope:
factories.cpp:65:2: error: 'll' does not name a type
  ll mn, v;
  ^
factories.cpp:69:10: error: expected ')' before 'mn'
  Node(ll mn, ll v) : mn(mn), v(v) {}
          ^
factories.cpp: In constructor 'Node::Node()':
factories.cpp:67:20: error: no matching function for call to 'Node::Node(int, int)'
   *this = Node(0, 0);
                    ^
factories.cpp:66:2: note: candidate: Node::Node()
  Node() {
  ^
factories.cpp:66:2: note:   candidate expects 0 arguments, 2 provided
factories.cpp:63:7: note: candidate: constexpr Node::Node(const Node&)
 class Node {
       ^
factories.cpp:63:7: note:   candidate expects 1 argument, 2 provided
factories.cpp:63:7: note: candidate: constexpr Node::Node(Node&&)
factories.cpp:63:7: note:   candidate expects 1 argument, 2 provided
factories.cpp: At global scope:
factories.cpp:72:50: error: 'll' has not been declared
 void update(int st, int en, int S, int E, int n, ll v) {
                                                  ^
factories.cpp: In function 'void update(int, int, int, int, int, int)':
factories.cpp:75:11: error: 'class Node' has no member named 'mn'
   indt[n].mn += v;
           ^
factories.cpp:76:11: error: 'class Node' has no member named 'v'
   indt[n].v += v;
           ^
factories.cpp:81:22: error: 'min' was not declared in this scope
  update(st, min(en, M), S, M, 2 * n, v);
                      ^
factories.cpp:81:22: note: suggested alternative:
In file included from /usr/include/c++/5/vector:60:0,
                 from factories.cpp:2:
/usr/include/c++/5/bits/stl_algobase.h:243:5: note:   'std::min'
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
factories.cpp:82:22: error: 'max' was not declared in this scope
  update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
                      ^
factories.cpp:82:22: note: suggested alternative:
In file included from /usr/include/c++/5/vector:60:0,
                 from factories.cpp:2:
/usr/include/c++/5/bits/stl_algobase.h:265:5: note:   'std::max'
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
factories.cpp:83:10: error: 'class Node' has no member named 'mn'
  indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn) + indt[n].v;
          ^
factories.cpp:83:31: error: 'class Node' has no member named 'mn'
  indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn) + indt[n].v;
                               ^
factories.cpp:83:51: error: 'class Node' has no member named 'mn'
  indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn) + indt[n].v;
                                                   ^
factories.cpp:83:65: error: 'class Node' has no member named 'v'
  indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn) + indt[n].v;
                                                                 ^
factories.cpp: At global scope:
factories.cpp:86:1: error: 'll' does not name a type
 ll qans;
 ^
factories.cpp:87:1: error: 'vector' does not name a type
 vector <int> Vv;
 ^
factories.cpp:88:1: error: 'vector' does not name a type
 vector <int> Vv2;
 ^
factories.cpp:89:1: error: 'vector' does not name a type
 vector <pll> conn2[500050];
 ^
factories.cpp:90:1: error: 'vector' does not name a type
 vector <pll> son2[500050];
 ^
factories.cpp:91:1: error: 'll' does not name a type
 ll dis[500050];
 ^
factories.cpp: In function 'void DFS2(int)':
factories.cpp:97:17: error: 'conn2' was not declared in this scope
  for (auto it : conn2[n]) {
                 ^
factories.cpp:99:3: error: 'son2' was not declared in this scope
   son2[n].push_back(it);
   ^
factories.cpp:100:3: error: 'dis' was not declared in this scope
   dis[it.second] = dis[n] + it.first;
   ^
factories.cpp: In function 'void DFS3(int)':
factories.cpp:106:20: error: 'qans' was not declared in this scope
  if (tchk[n] == 1) qans = min(qans, indt[1].mn);
                    ^
factories.cpp:106:45: error: 'class Node' has no member named 'mn'
  if (tchk[n] == 1) qans = min(qans, indt[1].mn);
                                             ^
factories.cpp:106:47: error: 'min' was not declared in this scope
  if (tchk[n] == 1) qans = min(qans, indt[1].mn);
                                               ^
factories.cpp:106:47: note: suggested alternative:
In file included from /usr/include/c++/5/vector:60:0,
                 from factories.cpp:2:
/usr/include/c++/5/bits/stl_algobase.h:243:5: note:   'std::min'
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
factories.cpp:107:17: error: 'son2' was not declared in this scope
  for (auto it : son2[n]) {
                 ^
factories.cpp:108:11: error: 'class Node' has no member named 'mn'
   indt[1].mn += it.first, indt[1].v += it.first;
           ^
factories.cpp:108:35: error: 'class Node' has no member named 'v'
   indt[1].mn += it.first, indt[1].v += it.first;
                                   ^
factories.cpp:109: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:111:11: error: 'class Node' has no member named 'mn'
   indt[1].mn -= it.first, indt[1].v -= it.first;
           ^
factories.cpp:111:35: error: 'class Node' has no member named 'v'
   indt[1].mn -= it.first, indt[1].v -= it.first;
                                   ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:116:2: error: 'Vv' was not declared in this scope
  Vv.reserve(2 * (S + T));
  ^
factories.cpp:117:2: error: 'Vv2' was not declared in this scope
  Vv2.reserve(S + T);
  ^
factories.cpp:121:13: error: 'all' was not declared in this scope
  sort(all(Vv), [](int a, int b) {
             ^
factories.cpp:123:3: error: 'sort' was not declared in this scope
  });
   ^
factories.cpp:125:72: error: 'lca' was not declared in this scope
  for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
                                                                        ^
factories.cpp:126:17: error: unable to deduce 'auto&&' from 'Vv2'
  for (auto it : Vv2) Vv.push_back(it);
                 ^
factories.cpp:130:25: error: 'unique' was not declared in this scope
  Vv.erase(unique(all(Vv)), Vv.end());
                         ^
factories.cpp:131:17: error: unable to deduce 'auto&&' from 'Vv'
  for (auto it : Vv) tchk[it] = 0;
                 ^
factories.cpp:138:15: error: 'lca' was not declared in this scope
   x = lca(x, y).second;
               ^
factories.cpp:139:3: error: 'pll' was not declared in this scope
   pll u = lca(x, y);
   ^
factories.cpp:140:3: error: 'conn2' was not declared in this scope
   conn2[x].emplace_back(u.first, y);
   ^
factories.cpp:140:25: error: 'u' was not declared in this scope
   conn2[x].emplace_back(u.first, y);
                         ^
factories.cpp:146:3: error: 'dis' was not declared in this scope
   dis[Vv[i]] = 0;
   ^
factories.cpp:150:7: error: 'IT_MAX' was not declared in this scope
  for (IT_MAX = 2; IT_MAX < Vv.size(); IT_MAX *= 2);
       ^
factories.cpp:151: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:151:54: error: no matching function for call to 'Node::Node(int, int)'
  for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node(0, 0);
                                                      ^
factories.cpp:66:2: note: candidate: Node::Node()
  Node() {
  ^
factories.cpp:66:2: note:   candidate expects 0 arguments, 2 provided
factories.cpp:63:7: note: candidate: constexpr Node::Node(const Node&)
 class Node {
       ^
factories.cpp:63:7: note:   candidate expects 1 argument, 2 provided
factories.cpp:63:7: note: candidate: constexpr Node::Node(Node&&)
factories.cpp:63:7: note:   candidate expects 1 argument, 2 provided
factories.cpp:153:3: error: 'll' was not declared in this scope
   ll v = dis[Vv[i]];
   ^
factories.cpp:154:26: error: 'v' was not declared in this scope
   if (tchk[Vv[i]] != -1) v = LL_INF;
                          ^
factories.cpp:154:30: error: 'LL_INF' was not declared in this scope
   if (tchk[Vv[i]] != -1) v = LL_INF;
                              ^
factories.cpp:156: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:156:54: error: 'v' was not declared in this scope
   update(lr2[Vv[i]][0], lr2[Vv[i]][0], 1, IT_MAX, 1, v);
                                                      ^
factories.cpp:158:24: error: 'IT_MAX' was not declared in this scope
  update(Vv.size() + 1, IT_MAX, 1, IT_MAX, 1, LL_INF);
                        ^
factories.cpp:158:46: error: 'LL_INF' was not declared in this scope
  update(Vv.size() + 1, IT_MAX, 1, IT_MAX, 1, LL_INF);
                                              ^
factories.cpp:159:2: error: 'qans' was not declared in this scope
  qans = LL_INF;
  ^
factories.cpp:162:17: error: unable to deduce 'auto&&' from 'Vv'
  for (auto it : Vv) {
                 ^
factories.cpp:163:3: error: 'conn2' was not declared in this scope
   conn2[it].clear();
   ^
factories.cpp:164:3: error: 'son2' was not declared in this scope
   son2[it].clear();
   ^
factories.cpp:118:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^