oj.uz

Submission #25296

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

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:7:9: error: 'pair' does not name a type
 typedef pair <ll, ll> pll;
         ^
factories.cpp:15:1: error: 'vector' does not name a type
 vector <pll> conn[500050];
 ^
factories.cpp: In function 'void DFS(int)':
factories.cpp:19:17: error: 'conn' was not declared in this scope
  for (auto it : conn[n]) {
                 ^
factories.cpp: At global scope:
factories.cpp:32: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:59:3: error: 'conn' was not declared in this scope
   conn[A[i]].emplace_back(D[i], B[i]);
   ^
factories.cpp:57:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
factories.cpp: In function 'void update(int, int, int, int, int, ll)':
factories.cpp:85:22: error: 'min' was not declared in this scope
  update(st, min(en, M), S, M, 2 * n, v);
                      ^
factories.cpp:85:22: note: suggested alternative:
In file included from /usr/include/c++/5/algorithm:62:0,
                 from factories.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:3451:5: note:   'std::min'
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^
factories.cpp:86:22: error: 'max' was not declared in this scope
  update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
                      ^
factories.cpp:86:22: note: suggested alternative:
In file included from /usr/include/c++/5/algorithm:62:0,
                 from factories.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:3463:5: note:   'std::max'
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^
factories.cpp: At global scope:
factories.cpp:91:1: error: 'vector' does not name a type
 vector <int> Vv;
 ^
factories.cpp:92:1: error: 'vector' does not name a type
 vector <int> Vv2;
 ^
factories.cpp:93:1: error: 'vector' does not name a type
 vector <pll> conn2[500050];
 ^
factories.cpp:94:1: error: 'vector' does not name a type
 vector <pll> son2[500050];
 ^
factories.cpp: In function 'void DFS2(int)':
factories.cpp:101:17: error: 'conn2' was not declared in this scope
  for (auto it : conn2[n]) {
                 ^
factories.cpp:103:3: error: 'son2' was not declared in this scope
   son2[n].push_back(it);
   ^
factories.cpp: In function 'void DFS3(int)':
factories.cpp:110:47: error: 'min' was not declared in this scope
  if (tchk[n] == 1) qans = min(qans, indt[1].mn);
                                               ^
factories.cpp:110:47: note: suggested alternative:
In file included from /usr/include/c++/5/algorithm:62:0,
                 from factories.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:3451:5: note:   'std::min'
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^
factories.cpp:111:17: error: 'son2' was not declared in this scope
  for (auto it : son2[n]) {
                 ^
factories.cpp:113: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:120:2: error: 'Vv' was not declared in this scope
  Vv.reserve(2 * (S + T));
  ^
factories.cpp:121:2: error: 'Vv2' was not declared in this scope
  Vv2.reserve(S + T);
  ^
factories.cpp:125:13: error: 'all' was not declared in this scope
  sort(all(Vv), [](int a, int b) {
             ^
factories.cpp:127:3: error: 'sort' was not declared in this scope
  });
   ^
factories.cpp:127:3: note: suggested alternative:
In file included from /usr/include/c++/5/algorithm:62:0,
                 from factories.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:4718:5: note:   'std::sort'
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
     ^
factories.cpp:129: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:130:17: error: unable to deduce 'auto&&' from 'Vv2'
  for (auto it : Vv2) Vv.push_back(it);
                 ^
factories.cpp:134:25: error: 'unique' was not declared in this scope
  Vv.erase(unique(all(Vv)), Vv.end());
                         ^
factories.cpp:134:25: note: suggested alternative:
In file included from /usr/include/c++/5/algorithm:62:0,
                 from factories.cpp:1:
/usr/include/c++/5/bits/stl_algo.h:1022:5: note:   'std::unique'
     unique(_ForwardIterator __first, _ForwardIterator __last,
     ^
factories.cpp:135:17: error: unable to deduce 'auto&&' from 'Vv'
  for (auto it : Vv) tchk[it] = 0;
                 ^
factories.cpp:142:15: error: 'lca' was not declared in this scope
   x = lca(x, y).second;
               ^
factories.cpp:143:3: error: 'pll' was not declared in this scope
   pll u = lca(x, y);
   ^
factories.cpp:144:3: error: 'conn2' was not declared in this scope
   conn2[x].emplace_back(u.first, y);
   ^
factories.cpp:144:25: error: 'u' was not declared in this scope
   conn2[x].emplace_back(u.first, y);
                         ^
factories.cpp:154:7: error: 'IT_MAX' was not declared in this scope
  for (IT_MAX = 2; IT_MAX < Vv.size(); IT_MAX *= 2);
       ^
factories.cpp:155: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:160: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:162:24: error: 'IT_MAX' was not declared in this scope
  update(Vv.size() + 1, IT_MAX, 1, IT_MAX, 1, LL_INF);
                        ^
factories.cpp:166:17: error: unable to deduce 'auto&&' from 'Vv'
  for (auto it : Vv) {
                 ^
factories.cpp:167:3: error: 'conn2' was not declared in this scope
   conn2[it].clear();
   ^
factories.cpp:168:3: error: 'son2' was not declared in this scope
   son2[it].clear();
   ^
factories.cpp:122:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^