fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <numeric>
  6. #include <set>
  7. #include <map>
  8. #include <queue>
  9. #include <iostream>
  10. #include <sstream>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <ctime>
  14. #include <cstring>
  15. #include <cctype>
  16. #include <cassert>
  17. #include <limits>
  18. #include <functional>
  19. #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
  20. #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
  21. #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
  22. #if defined(_MSC_VER) || __cplusplus > 199711L
  23. #define aut(r,v) auto r = (v)
  24. #else
  25. #define aut(r,v) typeof(v) r = (v)
  26. #endif
  27. #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
  28. #define all(o) (o).begin(), (o).end()
  29. #define pb(x) push_back(x)
  30. #define mp(x,y) make_pair((x),(y))
  31. #define mset(m,v) memset(m,v,sizeof(m))
  32. #define INF 0x3f3f3f3f
  33. #define INFL 0x3f3f3f3f3f3f3f3fLL
  34. using namespace std;
  35. typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii;
  36. typedef long long ll; typedef vector<long long> vl; typedef pair<long long, long long> pll; typedef vector<pair<long long, long long> > vpll;
  37. typedef vector<string> vs; typedef long double ld;
  38. template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
  39. template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
  40.  
  41.  
  42. struct Xor128 {
  43. 	unsigned x, y, z, w;
  44. 	Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { }
  45. 	unsigned next() {
  46. 		unsigned t = x ^ (x << 11);
  47. 		x = y; y = z; z = w;
  48. 		return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
  49. 	}
  50. 	//手抜き
  51. 	inline unsigned next(unsigned n) { return next() % n; }
  52. };
  53.  
  54. //bottom upなTreap
  55. //脱再帰！
  56. //randomized binary searchにするにはchoiceRandomlyを
  57. //	bool choiceRandomly(Ref l, Ref r) { return rng.next(l->size + r->size) < l->size; }
  58. //に書き換えるだけでよい。
  59. template<typename Node>
  60. struct BottomupTreap {
  61. 	Xor128 rng;
  62. 	typedef Node *Ref;
  63. 	static int size(Ref t) { return !t ? 0 : t->size; }
  64.  
  65. 	unsigned nextRand() { return rng.next(); }
  66. private:
  67. 	bool choiceRandomly(Ref l, Ref r) {
  68. 		return l->priority < r->priority;
  69. 	}
  70. public:
  71.  
  72. 	Ref join(Ref l, Ref r) {
  73. 		if(!l) return r;
  74. 		if(!r) return l;
  75.  
  76. 		Ref t = NULL;
  77. 		unsigned long long dirs = 0;
  78. 		int h;
  79. 		for(h = 0; ; ++ h) {
  80. 			if(h >= sizeof(dirs)*8 - 2) {
  81. 				//dirsのオーバーフローを防ぐために再帰する。
  82. 				//あくまでセーフティガードなのでバランスは多少崩れるかもしれない
  83. 				t = join(l->right, r->left);
  84. 				dirs = dirs << 2 | 1;
  85. 				h ++;
  86. 				break;
  87. 			}
  88. 			dirs <<= 1;
  89. 			if(choiceRandomly(l, r)) {
  90. 				Ref c = l->right;
  91. 				if(!c) {
  92. 					t = r;
  93. 					r = r->parent;
  94. 					break;
  95. 				}
  96. 				l = c;
  97. 			}else {
  98. 				dirs |= 1;
  99. 				Ref c = r->left;
  100. 				if(!c) {
  101. 					t = l;
  102. 					l = l->parent;
  103. 					break;
  104. 				}
  105. 				r = c;
  106. 			}
  107. 		}
  108. 		for(; h >= 0; -- h) {
  109. 			if(!(dirs & 1)) {
  110. 				Ref p = l->parent;
  111. 				t = l->linkr(t);
  112. 				l = p;
  113. 			}else {
  114. 				Ref p = r->parent;
  115. 				t = r->linkl(t);
  116. 				r = p;
  117. 			}
  118. 			dirs >>= 1;
  119. 		}
  120. 		return t;
  121. 	}
  122.  
  123. 	typedef std::pair<Ref,Ref> RefPair;
  124.  
  125. 	//l＜t≦rの(l,r)に分割する
  126. 	RefPair split2(Ref t) {
  127. 		Ref p, l = t->left, r = t;
  128. 		Node::cut(l); t->linkl(NULL);
  129. 		while(p = t->parent) {
  130. 			t->parent = NULL;
  131. 			if(p->left == t)
  132. 				r = p->linkl(r);
  133. 			else
  134. 				l = p->linkr(l);
  135. 			t = p;
  136. 		}
  137. 		return RefPair(l, r);
  138. 	}
  139. 	//l＜t＜rの(l,t,r)に分割する。(l,r)を返す
  140. 	RefPair split3(Ref t) {
  141. 		Ref p, l = t->left, r = t->right;
  142. 		Node::cut(l), Node::cut(r);
  143. 		t->linklr(NULL, NULL);
  144. 		while(p = t->parent) {
  145. 			t->parent = NULL;
  146. 			if(p->left == t)
  147. 				r = p->linkl(r);
  148. 			else
  149. 				l = p->linkr(l);
  150. 			t = p;
  151. 		}
  152. 		return RefPair(l, r);
  153. 	}
  154. 	Ref cons(Ref h, Ref t) {
  155. 		assert(size(h) == 1);
  156. 		if(!t) return h;
  157. 		Ref u = NULL;
  158. 		while(true) {
  159. 			if(choiceRandomly(h, t)) {
  160. 				Ref p = t->parent;
  161. 				u = h->linkr(t);
  162. 				t = p;
  163. 				break;
  164. 			}
  165. 			Ref l = t->left;
  166. 			if(!l) {
  167. 				u = h;
  168. 				break;
  169. 			}
  170. 			t = l;
  171. 		}
  172. 		while(t) {
  173. 			u = t->linkl(u);
  174. 			t = t->parent;
  175. 		}
  176. 		return u;
  177. 	}
  178. };
  179.  
  180. //free treeのために、辺を基本として扱う
  181. class EulerTourTreeWithMarks {
  182. 	struct Node {
  183. 		typedef BottomupTreap<Node> BST;
  184.  
  185. 		Node *left, *right, *parent;
  186. 		int size;
  187. 		unsigned priority;
  188. 		char marks, markUnions;	//0ビット目がedgeMark, 1ビット目がvertexMark
  189.  
  190. 		Node(): left(NULL), right(NULL), parent(NULL),
  191. 			size(1), priority(0), marks(0), markUnions(0) { }
  192.  
  193. 		inline Node *update() {
  194. 			int size_t = 1, markUnions_t = marks;
  195. 			if(left) {
  196. 				size_t += left->size;
  197. 				markUnions_t |= left->markUnions;
  198. 			}
  199. 			if(right) {
  200. 				size_t += right->size;
  201. 				markUnions_t |= right->markUnions;
  202. 			}
  203. 			size = size_t, markUnions = markUnions_t;
  204. 			return this;
  205. 		}
  206.  
  207. 		inline Node *linkl(Node *c) {
  208. 			if(left = c) c->parent = this;
  209. 			return update();
  210. 		}
  211. 		inline Node *linkr(Node *c) {
  212. 			if(right = c) c->parent = this;
  213. 			return update();
  214. 		}
  215. 		inline Node *linklr(Node *l, Node *r) {
  216. 			if(left = l) l->parent = this;
  217. 			if(right = r) r->parent = this;
  218. 			return update();
  219. 		}
  220. 		static Node *cut(Node *t) {
  221. 			if(t) t->parent = NULL;
  222. 			return t;
  223. 		}
  224.  
  225. 		static const Node *findRoot(const Node *t) {
  226. 			while(t->parent) t = t->parent;
  227. 			return t;
  228. 		}
  229. 		static std::pair<Node*,int> getPosition(Node *t) {
  230. 			int k = BST::size(t->left);
  231. 			Node *p;
  232. 			while(p = t->parent) {
  233. 				if(p->right == t)
  234. 					k += BST::size(p->left) + 1;
  235. 				t = p;
  236. 			}
  237. 			return std::make_pair(t, k);
  238. 		}
  239. 		static const Node *findHead(const Node *t) {
  240. 			while(t->left) t = t->left;
  241. 			return t;
  242. 		}
  243. 		static void updatePath(Node *t) {
  244. 			while(t) {
  245. 				t->update();
  246. 				t = t->parent;
  247. 			}
  248. 		}
  249. 		static int getPosition(const Node *t) {
  250. 			int k = t->left ? t->left->size : 0;
  251. 			while(1) {
  252. 				const Node *p = t->parent;
  253. 				if(!p) return k;
  254. 				if(p->right == t)
  255. 					k += (p->left ? p->left->size : 0) + 1;
  256. 				t = p;
  257. 			}
  258. 		}
  259. 	};
  260.  
  261. 	typedef Node::BST BST;
  262. 	BST bst;
  263.  
  264. 	std::vector<Node> nodes;
  265. 	//各頂点に対してその頂点から出ているarcを1つだけ代表として持つ(無い場合は-1)
  266. 	//逆にarcに対して対応する頂点はたかだか1つである
  267. 	std::vector<int> firstArc;
  268. 	//辺・頂点に対する属性
  269. 	std::vector<bool> edgeMark, vertexMark;
  270.  
  271. 	inline int getArcIndex(const Node *a) const { return a - &nodes[0]; }
  272.  
  273. 	inline int arc1(int ei) const { return ei; }
  274. 	inline int arc2(int ei) const { return ei + (numVertices() - 1); }
  275.  
  276. public:
  277. 	inline int numVertices() const { return firstArc.size(); }
  278. 	inline int numEdges() const { return numVertices() - 1; }
  279.  
  280. 	inline bool getEdgeMark(int a) const {
  281. 		return a < numEdges() ? edgeMark[a] : false;
  282. 	}
  283. 	inline bool getVertexMark(int v) const {
  284. 		return vertexMark[v];
  285. 	}
  286. private:
  287.  
  288. 	void updateMarks(int a, int v) {
  289. 		Node *t = &nodes[a];
  290. 		t->marks = getEdgeMark(a) << 0 | getVertexMark(v) << 1;
  291. 		Node::updatePath(t);
  292. 	}
  293.  
  294. 	//firstArcの変更に応じて更新する
  295. 	void firstArcChanged(int v, int a, int b) {
  296. 		if(a != -1) updateMarks(a, v);
  297. 		if(b != -1) updateMarks(b, v);
  298. 	}
  299.  
  300. public:
  301. 	class TreeRef {
  302. 		friend class EulerTourTreeWithMarks;
  303. 		const Node *ref;
  304. 	public:
  305. 		TreeRef() { }
  306. 		TreeRef(const Node *ref_): ref(ref_) { }
  307. 		bool operator==(const TreeRef &that) const { return ref == that.ref; }
  308. 		bool operator!=(const TreeRef &that) const { return ref != that.ref; }
  309. 		bool isIsolatedVertex() const { return ref == NULL; }
  310. 	};
  311.  
  312. 	void init(int N) {
  313. 		int M = N - 1;
  314. 		firstArc.assign(N, -1);
  315. 		nodes.assign(M * 2, Node());
  316. 		for(int i = 0; i < M * 2; i ++)
  317. 			nodes[i].priority = bst.nextRand();
  318. 		edgeMark.assign(M, false);
  319. 		vertexMark.assign(N, false);
  320. 	}
  321.  
  322. 	TreeRef getTreeRef(int v) const {
  323. 		int a = firstArc[v];
  324. 		return TreeRef(a == -1 ? NULL : Node::findRoot(&nodes[a]));
  325. 	}
  326.  
  327. 	bool isConnected(int v, int w) const {
  328. 		if(v == w) return true;
  329. 		int a = firstArc[v], b = firstArc[w];
  330. 		if(a == -1 || b == -1) return false;
  331. 		return Node::findRoot(&nodes[a]) == Node::findRoot(&nodes[b]);
  332. 	}
  333.  
  334. 	int getTreeFirstArc(TreeRef t) const {
  335. 		assert(!t.isIsolatedVertex());
  336. 		return getArcIndex(t.ref);
  337. 	}
  338.  
  339. 	static int getSize(TreeRef t) {
  340. 		if(t.isIsolatedVertex()) return 1;
  341. 		else return t.ref->size / 2 + 1;
  342. 	}
  343.  
  344. 	int getPosition(int v) const {
  345. 		int a = firstArc[v];
  346. 		if(a == -1) return 0;
  347. 		return Node::getPosition(&nodes[a]);
  348. 	}
  349.  
  350. 	void link(int ti, int v, int w) {
  351. 		int a1 = arc1(ti), a2 = arc2(ti);
  352. 		//v→wがa1に対応するようにする
  353. 		if(v > w) std::swap(a1, a2);
  354.  
  355. 		int va = firstArc[v], wa = firstArc[w];
  356.  
  357. 		Node *l, *m, *r;
  358. 		if(va != -1) {
  359. 			//evert。順番を入れ替えるだけ
  360. 			std::pair<Node*,Node*> p = bst.split2(&nodes[va]);
  361. 			m = bst.join(p.second, p.first);
  362. 		}else {
  363. 			//vが孤立点の場合
  364. 			m = NULL;
  365. 			firstArc[v] = a1;
  366. 			firstArcChanged(v, -1, a1);
  367. 		}
  368. 		if(wa != -1) {
  369. 			std::pair<Node*,Node*> p = bst.split2(&nodes[wa]);
  370. 			l = p.first, r = p.second;
  371. 		}else {
  372. 			//wが孤立点の場合
  373. 			l = r = NULL;
  374. 			firstArc[w] = a2;
  375. 			firstArcChanged(w, -1, a2);
  376. 		}
  377. 		//w→vの辺をmの先頭＝lの末尾にinsert
  378. 		m = bst.cons(&nodes[a2], m);
  379. 		//v→wの辺をmの末尾＝rの先頭にinsert
  380. 		r = bst.cons(&nodes[a1], r);
  381.  
  382. 		bst.join(bst.join(l, m), r);
  383. 	}
  384.  
  385. 	void cut(int ti, int v, int w) {
  386. 		//v→wがa1に対応するようにする
  387. 		if(v > w) std::swap(v, w);
  388.  
  389. 		int a1 = arc1(ti), a2 = arc2(ti);
  390. 		std::pair<Node*,Node*> p = bst.split3(&nodes[a1]);
  391. 		int prsize = BST::size(p.second);
  392. 		std::pair<Node*,Node*> q = bst.split3(&nodes[a2]);
  393. 		Node *l, *m, *r;
  394. 		//a1,a2の順番を判定する。a1＜a2ならp.secondが変わっているはず
  395. 		if(p.second == &nodes[a2] || BST::size(p.second) != prsize) {
  396. 			l = p.first, m = q.first, r = q.second;
  397. 		}else {
  398. 			//a2＜a1の順番である。v→wの辺がa1であって親→子であることにする
  399. 			std::swap(v, w);
  400. 			std::swap(a1, a2);
  401. 			l = q.first, m = q.second, r = p.second;
  402. 		}
  403.  
  404. 		//firstArcを必要に応じて書き換える
  405. 		if(firstArc[v] == a1) {
  406. 			int b;
  407. 			if(r != NULL) {
  408. 				//vが根じゃないなら右側の最初の辺でよい
  409. 				b = getArcIndex(Node::findHead(r));
  410. 			}else {
  411. 				//vが根なら最初の辺でよい。孤立点になるなら-1
  412. 				b = !l ? -1 : getArcIndex(Node::findHead(l));
  413. 			}
  414. 			firstArc[v] = b;
  415. 			firstArcChanged(v, a1, b);
  416. 		}
  417. 		if(firstArc[w] == a2) {
  418. 			//wが根になるので最初の辺でよい。孤立点になるなら-1
  419. 			int b = !m ? -1 : getArcIndex(Node::findHead(m));
  420. 			firstArc[w] = b;
  421. 			firstArcChanged(w, a2, b);
  422. 		}
  423.  
  424. 		bst.join(l, r);
  425. 	}
  426.  
  427. 	void changeEdgeMark(int ti, bool b) {
  428. 		assert(ti < numEdges());
  429. 		edgeMark[ti] = b;
  430. 		Node *t = &nodes[ti];
  431. 		t->marks = (b << 0) | (t->marks & (1 << 1));
  432. 		Node::updatePath(t);
  433. 	}
  434. 	void changeVertexMark(int v, bool b) {
  435. 		vertexMark[v] = b;
  436. 		int a = firstArc[v];
  437. 		if(a != -1) {
  438. 			Node *t = &nodes[a];
  439. 			t->marks = (t->marks & (1 << 0)) | (b << 1);
  440. 			Node::updatePath(t);
  441. 		}
  442. 	}
  443.  
  444. 	template<typename Callback>
  445. 	bool enumMarkedEdges(TreeRef tree, Callback callback) const {
  446. 		return enumMarks<0,Callback>(tree, callback);
  447. 	}
  448. 	//孤立点の場合は呼び側でその頂点だけ処理する必要がある
  449. 	template<typename Callback>
  450. 	bool enumMarkedVertices(TreeRef tree, Callback callback) const {
  451. 		return enumMarks<1,Callback>(tree, callback);
  452. 	}
  453. private:
  454. 	//callback : TreeEdgeIndex×2 -> Bool
  455. 	//引数は頂点をそこからのincident arcで示し、"(正方向 ? 0 : N-1) + treeEdgeIndex"を表す。方向はv,wの大小で処理すればよい
  456. 	//callbackは継続するかどうかをboolで返す。最後まで列挙し終えたかどうかを返す。
  457. 	template<int Mark, typename Callback>
  458. 	bool enumMarks(TreeRef tree, Callback callback) const {
  459. 		if(tree.isIsolatedVertex()) return true;
  460. 		const Node *t = tree.ref;
  461. 		if(t->markUnions >> Mark & 1)
  462. 			return enumMarksRec<Mark,Callback>(t, callback);
  463. 		else
  464. 			return true;
  465. 	}
  466.  
  467. 	//平衡木なので深さは深くないので再帰して問題ない
  468. 	template<int Mark, typename Callback>
  469. 	bool enumMarksRec(const Node *t, Callback callback) const {
  470. 		const Node *l = t->left, *r = t->right;
  471. 		if(l && (l->markUnions >> Mark & 1))
  472. 			if(!enumMarksRec<Mark,Callback>(l, callback)) return false;
  473. 		if(t->marks >> Mark & 1)
  474. 			if(!callback(getArcIndex(t))) return false;
  475. 		if(r && (r->markUnions >> Mark & 1))
  476. 			if(!enumMarksRec<Mark,Callback>(r, callback)) return false;
  477. 		return true;
  478. 	}
  479.  
  480. public:
  481. 	//デバッグ用
  482. 	void debugEnumEdges(std::vector<int> &out_v) const {
  483. 		int M = numEdges();
  484. 		for(int ti = 0; ti < M; ti ++) {
  485. 			const Node *t = &nodes[ti];
  486. 			if(t->left || t->right || t->parent)
  487. 				out_v.push_back(ti);
  488. 		}
  489. 	}
  490. };
  491.  
  492. //treeEdgeにはそれぞれ0～N-1のインデックスが与えられる。これは全てのレベルで共通。
  493. //ところで"level up"って和製英語なんだ。promoteでいいかな。
  494. //Sampling heuristic ランダムケースで超速く(4倍とか)なったんだけど！いいね！
  495. class HolmDeLichtenbergThorup {
  496. 	typedef HolmDeLichtenbergThorup This;
  497. 	typedef EulerTourTreeWithMarks Forest;
  498. 	typedef Forest::TreeRef TreeRef;
  499.  
  500. 	int numVertices_m;
  501. 	int numSamplings;
  502.  
  503. 	//DynamicTreeはコピーできないけどまあその状態で使わなきゃいいじゃんということで…
  504. 	std::vector<Forest> forests;
  505.  
  506. 	std::vector<char> edgeLevel;
  507. 	std::vector<int> treeEdgeIndex;	// : EdgeIndex -> TreeEdgeIndex
  508. 	std::vector<int> treeEdgeMap;	// : TreeEdgeIndex -> EdgeIndex
  509. 	std::vector<int> treeEdgeIndexFreeList;	// : [TreeEdgeIndex]
  510.  
  511. 	//arcも方向はEulerTourTreeと同じようにv,wの大小に合わせる
  512. 	std::vector<int> arcHead;
  513.  
  514. 	std::vector<std::vector<int> > firstIncidentArc;
  515. 	std::vector<int> nextIncidentArc, prevIncidentArc;
  516.  
  517. 	//一時的に使う。使い回して使う
  518. 	std::vector<bool> edgeVisited;
  519. 	std::vector<int> visitedEdges;	// : [EdgeIndex | TreeEdgeIndex]
  520.  
  521. 	int arc1(int ei) const { return ei; }
  522. 	int arc2(int ei) const { return numMaxEdges() + ei; }
  523. 	int arcEdge(int i) const { return i >= numMaxEdges() ? i - numMaxEdges() : i; }
  524.  
  525. 	bool replace(int lv, int v, int w) {
  526. 		Forest &forest = forests[lv];
  527.  
  528. 		TreeRef vRoot = forest.getTreeRef(v), wRoot = forest.getTreeRef(w);
  529. 		assert(vRoot.isIsolatedVertex() || wRoot.isIsolatedVertex() || vRoot != wRoot);
  530.  
  531. 		int vSize = forest.getSize(vRoot), wSize = forest.getSize(wRoot);
  532.  
  533. 		int u; TreeRef uRoot; int uSize;
  534. 		if(vSize <= wSize)
  535. 			u = v, uRoot = vRoot, uSize = vSize;
  536. 		else
  537. 			u = w, uRoot = wRoot, uSize = wSize;
  538.  
  539. 		//replacement edgeを探す
  540. 		int replacementEdge = -1;
  541. 		enumIncidentArcs(forest, uRoot, u, lv, FindReplacementEdge(uRoot, &replacementEdge));
  542.  
  543. 		//"Sampling heuristic"
  544. 		//早い時点で見つかったならT_u,他のincident arcsをレベルアップさせなくても計算量的に問題ない
  545. 		if(replacementEdge != -1 && (int)visitedEdges.size() + 1 <= numSamplings) {
  546. 			//replacementEdgeを処理する
  547. 			deleteNontreeEdge(replacementEdge);
  548. 			addTreeEdge(replacementEdge);
  549. 			for(int i = 0; i < (int)visitedEdges.size(); i ++)
  550. 				edgeVisited[visitedEdges[i]] = false;
  551. 			visitedEdges.clear();
  552. 			return true;
  553. 		}
  554.  
  555. 		//見つけたincident arcsを一斉にレベルアップさせる。edgeVisitedの後処理もする
  556. 		for(int i = 0; i < (int)visitedEdges.size(); i ++) {
  557. 			int ei = visitedEdges[i];
  558. 			edgeVisited[ei] = false;
  559.  
  560. 			deleteNontreeEdge(ei);
  561.  
  562. 			++ edgeLevel[ei];
  563.  
  564. 			insertNontreeEdge(ei);
  565. 		}
  566. 		visitedEdges.clear();
  567.  
  568. 		//このレベルのT_uの辺を列挙する
  569. 		forest.enumMarkedEdges(uRoot, EnumLevelTreeEdges(this));
  570. 		//列挙したT_uの辺を一斉にレベルアップさせる
  571. 		for(int i = 0; i < (int)visitedEdges.size(); i ++) {
  572. 			int ti = visitedEdges[i];
  573.  
  574. 			int ei = treeEdgeMap[ti];
  575. 			int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
  576. 			int lv = edgeLevel[ei];
  577.  
  578. 			edgeLevel[ei] = lv + 1;
  579.  
  580. 			forests[lv].changeEdgeMark(ti, false);
  581. 			forests[lv+1].changeEdgeMark(ti, true);
  582.  
  583. 			forests[lv+1].link(ti, v, w);
  584. 		}
  585. 		visitedEdges.clear();
  586.  
  587. 		if(replacementEdge != -1) {
  588. 			//T_uの辺列挙の前に構造が変わると困るのでreplacementEdgeはこのタイミングで処理する
  589. 			deleteNontreeEdge(replacementEdge);
  590. 			addTreeEdge(replacementEdge);
  591. 			return true;
  592. 		}else if(lv > 0) {
  593. 			return replace(lv-1, v, w);
  594. 		}else {
  595. 			return false;
  596. 		}
  597. 	}
  598.  
  599. 	struct EnumLevelTreeEdges {
  600. 		This *thisp;
  601. 		EnumLevelTreeEdges(This *thisp_): thisp(thisp_) { }
  602.  
  603. 		inline bool operator()(int a) {
  604. 			thisp->enumLevelTreeEdges(a);
  605. 			return true;
  606. 		}
  607. 	};
  608. 	void enumLevelTreeEdges(int ti) {
  609. 		visitedEdges.push_back(ti);
  610. 	}
  611.  
  612. 	//孤立点の時特別な処理をするなどしなければいけないのでヘルパー
  613. 	template<typename Callback>
  614. 	bool enumIncidentArcs(Forest &forest, TreeRef t, int u, int lv, Callback callback) {
  615. 		if(t.isIsolatedVertex())
  616. 			return enumIncidentArcsWithVertex<Callback>(lv, u, callback);
  617. 		else
  618. 			return forest.enumMarkedVertices(t, EnumIncidentArcs<Callback>(this, lv, callback));
  619. 	}
  620.  
  621. 	template<typename Callback>
  622. 	struct EnumIncidentArcs {
  623. 		This *thisp;
  624. 		int lv;
  625. 		Callback callback;
  626.  
  627. 		EnumIncidentArcs(This *thisp_, int lv_, Callback callback_):
  628. 			thisp(thisp_), lv(lv_), callback(callback_) { }
  629.  
  630. 		inline bool operator()(int tii) const {
  631. 			return thisp->enumIncidentArcsWithTreeArc(tii, lv, callback);
  632. 		}
  633. 	};
  634.  
  635. 	template<typename Callback>
  636. 	bool enumIncidentArcsWithTreeArc(int tii, int lv, Callback callback) {
  637. 		int u = getTreeEdgeIndexTailVertex(tii);
  638. 		return enumIncidentArcsWithVertex(lv, u, callback);
  639. 	}
  640.  
  641. 	int getTreeEdgeIndexTailVertex(int tii) const {
  642. 		bool dir = tii >= numVertices() - 1;
  643. 		int ti = dir ? tii - (numVertices() - 1) : tii;
  644. 		int ei = treeEdgeMap[ti];
  645. 		int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
  646. 		//方向を求め、そのarcのtailの頂点を取得する
  647. 		int u = !(dir != (v > w)) ? v : w;
  648. 		return u;
  649. 	}
  650.  
  651. 	//1つの頂点を処理する
  652. 	template<typename Callback>
  653. 	bool enumIncidentArcsWithVertex(int lv, int u, Callback callback) {
  654. 		int it = firstIncidentArc[lv][u];
  655. 		while(it != -1) {
  656. 			if(!callback(this, it))
  657. 				return false;
  658. 			it = nextIncidentArc[it];
  659. 		}
  660. 		return true;
  661. 	}
  662.  
  663. 	struct FindReplacementEdge {
  664. 		TreeRef uRoot;
  665. 		int *replacementEdge;
  666. 		FindReplacementEdge(TreeRef uRoot_, int *replacementEdge_):
  667. 			uRoot(uRoot_), replacementEdge(replacementEdge_) { }
  668.  
  669. 		inline bool operator()(This *thisp, int a) const {
  670. 			return thisp->findReplacementEdge(a, uRoot, replacementEdge);
  671. 		}
  672. 	};
  673.  
  674. 	//1つのarcを処理する
  675. 	bool findReplacementEdge(int a, TreeRef uRoot, int *replacementEdge) {
  676. 		int ei = arcEdge(a);
  677. 		if(edgeVisited[ei]) return true;
  678.  
  679. 		int lv = edgeLevel[ei];
  680. 		TreeRef hRoot = forests[lv].getTreeRef(arcHead[a]);
  681.  
  682. 		if(hRoot.isIsolatedVertex() || hRoot != uRoot) {
  683. 			//別の木に渡されているならreplacement edgeである。
  684. 			*replacementEdge = ei;
  685. 			return false;
  686. 		}
  687. 		//replacement edgeはvisitedEdgesに入れたくないのでこの位置でマークする
  688. 		edgeVisited[ei] = true;
  689. 		visitedEdges.push_back(ei);
  690. 		return true;
  691. 	}
  692.  
  693. 	void addTreeEdge(int ei) {
  694. 		int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
  695. 		int lv = edgeLevel[ei];
  696.  
  697. 		int ti = treeEdgeIndexFreeList.back();
  698. 		treeEdgeIndexFreeList.pop_back();
  699. 		treeEdgeIndex[ei] = ti;
  700. 		treeEdgeMap[ti] = ei;
  701.  
  702. 		forests[lv].changeEdgeMark(ti, true);
  703.  
  704. 		for(int i = 0; i <= lv; i ++)
  705. 			forests[i].link(ti, v, w);
  706. 	}
  707.  
  708. 	void insertIncidentArc(int a, int v) {
  709. 		int ei = arcEdge(a);
  710. 		int lv = edgeLevel[ei];
  711. 		assert(treeEdgeIndex[ei] == -1);
  712.  
  713. 		int next = firstIncidentArc[lv][v];
  714. 		firstIncidentArc[lv][v] = a;
  715. 		nextIncidentArc[a] = next;
  716. 		prevIncidentArc[a] = -1;
  717. 		if(next != -1) prevIncidentArc[next] = a;
  718.  
  719. 		if(next == -1)
  720. 			forests[lv].changeVertexMark(v, true);
  721. 	}
  722.  
  723. 	void deleteIncidentArc(int a, int v) {
  724. 		int ei = arcEdge(a);
  725. 		int lv = edgeLevel[ei];
  726. 		assert(treeEdgeIndex[ei] == -1);
  727.  
  728. 		int next = nextIncidentArc[a], prev = prevIncidentArc[a];
  729. 		nextIncidentArc[a] = prevIncidentArc[a] = -2;
  730.  
  731. 		if(next != -1) prevIncidentArc[next] = prev;
  732. 		if(prev != -1) nextIncidentArc[prev] = next;
  733. 		else firstIncidentArc[lv][v] = next;
  734.  
  735. 		if(next == -1 && prev == -1)
  736. 			forests[lv].changeVertexMark(v, false);
  737. 	}
  738.  
  739. 	void insertNontreeEdge(int ei) {
  740. 		int a1 = arc1(ei), a2 = arc2(ei);
  741. 		insertIncidentArc(a1, arcHead[a2]);
  742. 		insertIncidentArc(a2, arcHead[a1]);
  743. 	}
  744.  
  745. 	void deleteNontreeEdge(int ei) {
  746. 		int a1 = arc1(ei), a2 = arc2(ei);
  747. 		deleteIncidentArc(a1, arcHead[a2]);
  748. 		deleteIncidentArc(a2, arcHead[a1]);
  749. 	}
  750.  
  751. public:
  752. 	HolmDeLichtenbergThorup(): numVertices_m(0), numSamplings(0) { }
  753.  
  754. 	int numVertices() const { return numVertices_m; }
  755. 	int numMaxEdges() const { return edgeLevel.size(); }
  756.  
  757. 	void init(int N, int M) {
  758. 		numVertices_m = N;
  759.  
  760. 		int levels = 1;
  761. 		while(1 << levels <= N / 2) levels ++;
  762.  
  763. 		//サンプリング数を設定する。適切な値はよくわからない
  764. 		numSamplings = (int)(levels * 1);
  765.  
  766. 		forests.resize(levels);
  767. 		for(int lv = 0; lv < levels; lv ++)
  768. 			forests[lv].init(N);
  769.  
  770. 		edgeLevel.assign(M, -1);
  771.  
  772. 		treeEdgeIndex.assign(M, -1);
  773. 		treeEdgeMap.assign(N - 1, -1);
  774.  
  775. 		treeEdgeIndexFreeList.resize(N-1);
  776. 		for(int ti = 0; ti < N-1; ti ++)
  777. 			treeEdgeIndexFreeList[ti] = ti;
  778.  
  779. 		arcHead.assign(M * 2, -1);
  780.  
  781. 		firstIncidentArc.resize(levels);
  782. 		for(int lv = 0; lv < levels; lv ++)
  783. 			firstIncidentArc[lv].assign(N, -1);
  784. 		nextIncidentArc.assign(M * 2, -2);
  785. 		prevIncidentArc.assign(M * 2, -2);
  786.  
  787. 		edgeVisited.assign(M, false);
  788. 	}
  789.  
  790. 	bool insertEdge(int ei, int v, int w) {
  791. 		assert(0 <= ei && ei < numMaxEdges() && 0 <= v && v < numVertices() && 0 <= w && w < numVertices());
  792. 		assert(edgeLevel[ei] == -1);
  793.  
  794. 		int a1 = arc1(ei), a2 = arc2(ei);
  795. 		arcHead[a1] = w, arcHead[a2] = v;
  796.  
  797. 		bool treeEdge = !forests[0].isConnected(v, w);
  798.  
  799. 		edgeLevel[ei] = 0;
  800. 		if(treeEdge) {
  801. 			addTreeEdge(ei);
  802. 		}else {
  803. 			treeEdgeIndex[ei] = -1;
  804. 			//ループは見たくないのでリストにも入れない
  805. 			if(v != w)
  806. 				insertNontreeEdge(ei);
  807. 		}
  808.  
  809. 		return treeEdge;
  810. 	}
  811.  
  812. 	bool deleteEdge(int ei) {
  813. 		assert(0 <= ei && ei < numMaxEdges() && edgeLevel[ei] != -1);
  814.  
  815. 		int a1 = arc1(ei), a2 = arc2(ei);
  816. 		int v = arcHead[a2], w = arcHead[a1];
  817.  
  818. 		int lv = edgeLevel[ei];
  819. 		int ti = treeEdgeIndex[ei];
  820.  
  821. 		bool splitted = false;
  822. 		if(ti != -1) {
  823. 			treeEdgeMap[ti] = -1;
  824. 			treeEdgeIndex[ei] = -1;
  825. 			treeEdgeIndexFreeList.push_back(ti);
  826.  
  827. 			for(int i = 0; i <= lv; i ++)
  828. 				forests[i].cut(ti, v, w);
  829.  
  830. 			forests[lv].changeEdgeMark(ti, false);
  831.  
  832. 			splitted = !replace(lv, v, w);
  833. 		}else {
  834. 			//ループはリストに入ってない
  835. 			if(v != w)
  836. 				deleteNontreeEdge(ei);
  837. 		}
  838.  
  839. 		arcHead[a1] = arcHead[a2] = -1;
  840. 		edgeLevel[ei] = -1;
  841.  
  842. 		return splitted;
  843. 	}
  844.  
  845. 	bool isConnected(int v, int w) const {
  846. 		return forests[0].isConnected(v, w);
  847. 	}
  848.  
  849. 	int findComponentRepresent(int v) const {
  850. 		assert(0 <= v && v < numVertices());
  851. 		TreeRef t = forests[0].getTreeRef(v);
  852. 		if(t.isIsolatedVertex()) {
  853. 			return v;
  854. 		}else {
  855. 			int tii = forests[0].getTreeFirstArc(t);
  856. 			return getTreeEdgeIndexTailVertex(tii);
  857. 		}
  858. 	}
  859.  
  860. 	bool getParity(int v) const {
  861. 		return forests[0].getPosition(v) % 2 != 0;
  862. 	}
  863.  
  864. 	void dbgForestO(std::ostream &o) const {
  865. 		int N = numVertices(), M = numMaxEdges();
  866. 		int levels = forests.size();
  867. 		std::vector<bool> visited(M, false);
  868. 		o << "graph {\n";
  869. 		for(int lv = 0; lv < levels; lv ++) {
  870. 			o << "subgraph cluster_" << lv << "{\n";
  871. 			o << "label = " << '"' << "level " << lv << '"' << ";\n";
  872. 			for(int u = 0; u < N; u ++) {
  873. 				o << '"' << lv << "_" << u << '"';
  874. 				o << "[label=" << u << "];\n";
  875.  
  876. 				int it = firstIncidentArc[lv][u];
  877. 				while(it != -1) {
  878. 					int ei = arcEdge(it);
  879. 					if(!visited[ei]) {
  880. 						visited[ei] = true;
  881. 						int v = arcHead[arc2(ei)], w = arcHead[arc1(ei)];
  882. 						o << '"' << lv << "_" << v << '"' << " -- " << '"' << lv << "_" << w << '"';
  883. 						o << " [style=dotted]" << ";\n";
  884. 					}
  885. 					it = nextIncidentArc[it];
  886. 				}
  887. 			}
  888. 			std::vector<int> edges;
  889. 			forests[lv].debugEnumEdges(edges);
  890. 			for(int i = 0; i < (int)edges.size(); i ++) {
  891. 				int ti = edges[i];
  892. 				int ei = treeEdgeMap[ti];
  893. 				assert(ei != -1);
  894. 				int lvi = edgeLevel[ei];
  895. 				int a1 = arc1(ei), a2 = arc2(ei);
  896. 				int v = arcHead[a2], w = arcHead[a1];
  897. 				o << '"' << lv << "_" << v << '"' << " -- " << '"' << lv << "_" << w << '"';
  898. //				o << " [style=" << (lvi == lv ? "solid" : "dashed") << "]";
  899. 				o << ";\n";
  900. 			}
  901. 			o << "}\n";
  902. 		}
  903. 		o << "}" << std::endl;
  904. 	}
  905. };
  906.  
  907. vector<int> sqrtSort(const vector<pair<int,int> > &q, const int S) {
  908. 	int n = q.size();
  909. 	vector<long long> pack(n);
  910. 	for(int i = 0; i < n; i ++) {
  911. 		pack[i] =
  912. 			(long long)(q[i].first/S) << 50 |
  913. 			(long long)((q[i].first/S & 1) == 0 ? q[i].second : (1<<25) - 1 - q[i].second) << 25 |
  914. 			i;
  915. 	}
  916. 	sort(all(pack));
  917. 	vector<int> res(n);
  918. 	for(int i = 0; i < n; i ++)
  919. 		res[i] = pack[i] & ((1 << 25) - 1);
  920. 	return res;
  921. }
  922.  
  923. int main() {
  924. 	int n, m, q;
  925. 	scanf("%d%d%d", &n, &m, &q);
  926. 	vpii edges(m);
  927. 	rep(i, m) {
  928. 		int x, y;
  929. 		scanf("%d%d", &x, &y), -- x, -- y;
  930. 		edges[i] = mp(x, y);
  931. 	}
  932. 	cerr << endl;
  933. 	vector<int> maximal(m+1, -1);
  934. 	HolmDeLichtenbergThorup hdt;
  935. 	hdt.init(n, m);
  936. 	int right = 0;
  937. 	rep(left, m+1) {
  938. 		while(right < m) {
  939. 			int ei = right;
  940. 			pii p = edges[ei];
  941. 			int x = p.first, y = p.second;
  942. 			if(hdt.isConnected(x, y)) {
  943. //				hdt.dbgForestO(cerr);
  944. //				cerr << left << ", "<< right << ", " << x << ", "<< y << ": " << hdt.getParity(x) << ", " << hdt.getParity(y) << endl;
  945. 				if(hdt.getParity(x) == hdt.getParity(y))
  946. 					break;
  947. 			}
  948. 			hdt.insertEdge(ei, x, y);
  949. 			++ right;
  950. 		}
  951. //		cerr << left << ": " << right << endl;
  952. 		maximal[left] = right;
  953. 		if(left == m) break;
  954. 		int ei = left;
  955. 		hdt.deleteEdge(ei);
  956. 	}
  957.  
  958. 	rep(i, q) {
  959. 		int l, r;
  960. 		scanf("%d%d", &l, &r), -- l;
  961. 		bool ans = maximal[l] >= r;
  962. 		puts(ans ? "Possible" : "Impossible");
  963. 	}
  964.  
  965. 	return 0;
  966. }
Runtime error #stdin #stdout #stderr 0s 3292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/xVBc3S
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!