Submission #164534

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

//・わりと遅い…まあでもlog^2 nといわれればそんな感じではある
//・サンプリングとTest-Allっぽいものを導入してみたけどうまくいってるのかわからない…
//
//References
//・Holm, Jacob, Kristian De Lichtenberg, and Mikkel Thorup. "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity." Journal of the ACM (JACM) 48.4 (2001): 723-760.
//・Thorup, Mikkel. "Near-optimal fully-dynamic graph connectivity." Proceedings of the thirty-second annual ACM symposium on Theory of computing. ACM, 2000.
class FullyDynamicConnectivity {
	//local search treeとglobalな構造は同じノードで表して、ternary search treeっぽくやる
	struct Node {
		Node *left, *right;	//local treeの子ノード
		Node *mid;			//所有するlocal treeの根
		Node *parent;		//local/global treeの親ノード
		int numLeafs;		//global tree上の子木の葉の数(たとえlocal tree上で親子関係があったとしても兄弟ノードの数は足されないことに注意)
		int treeEdges, nonTreeEdges;	//ビットセットで、ビットiはlocal treeとglobal tree上の子孫の頂点にレベルiの木(resp.非木)辺が1つ以上接しているかを表す
		int level;			//global tree上のレベル
		Node():
			left(NULL), right(NULL), mid(NULL), parent(NULL),
			numLeafs(0), treeEdges(0), nonTreeEdges(0), level(-1) { }
	};
	std::vector<Node> vertexNodes;
	std::vector<bool> isTreeEdge;
	//その辺が存在しないことを-1で表す
	std::vector<int> edgeLevel;
	//無向辺: edge, 有向辺: arc と呼び分けることにする
	//arcの先の頂点
	std::vector<int> arcHead;		//Edge×2 → Vertex
	//頂点ごとにレベルごとにtree/non tree edgesが存在するかどうかのbitset
	std::vector<int> levelTreeEdges, levelNonTreeEdges;	//Vertex -> Bitset
	//頂点ごとのincident arcsの連結リスト
	std::vector<int> firstTreeArc, firstNonTreeArc;	//Vertex → Edge×2＋⊥
	//特定のレベルのリストをO(log n)で取得できるようにするために、連結リストを2段階にする
	//nextLevelArc,prevLevelArcはlevelごとの最初のエントリーにのみ保持される
	std::vector<int> nextLevelArc, nextPeerArc, prevLevelArc, prevPeerArc;	//Edge×2 → Edge×2＋⊥
	//使いまわして使う一時的なもの。サイズはそれぞれM, N
	std::vector<bool> edgeVisited, vertexVisited;
	//internal nodeたち
	std::vector<Node> internalNodes;
	std::vector<Node*> internalNodeFreeList;

	bool isLocalRoot(const Node *a) const {
		return !a->parent || a->parent->mid == a;
	}

	void updateNode(Node *a) const {
		int v = getVertexIndex(a);
		int treeEdges = 0, nonTreeEdges = 0;
		if(a->left) {
			treeEdges |= a->left->treeEdges;
			nonTreeEdges |= a->left->nonTreeEdges;
		}
		if(a->mid) {
			treeEdges |= a->mid->treeEdges;
			nonTreeEdges |= a->mid->nonTreeEdges;
		}
		if(a->right) {
			treeEdges |= a->right->treeEdges;
			nonTreeEdges |= a->right->nonTreeEdges;
		}
		if(v != -1) {
			treeEdges |= levelTreeEdges[v];
			nonTreeEdges |= levelNonTreeEdges[v];
		}
		a->treeEdges = treeEdges;
		a->nonTreeEdges = nonTreeEdges;
	}

	//rotateはupdateしない
	void rotateR(Node *a) const {
		Node *q = a->parent, *r = q->parent;
		if(q->left = a->right) a->right->parent = q;
		a->right = q; q->parent = a;
		if(a->parent = r) {
			if(r->left == q) r->left = a;
			else if(r->right == q) r->right = a;
			else if(r->mid == q) r->mid = a;
		}
	}
	void rotateL(Node *a) const {
		Node *q = a->parent, *r = q->parent;
		if(q->right = a->left) a->left->parent = q;
		a->left = q; q->parent = a;
		if(a->parent = r) {
			if(r->left == q) r->left = a;
			else if(r->right == q) r->right = a;
			else if(r->mid == q) r->mid = a;
		}
	}

	//localなsplay
	void localSplay(Node *a) {
		//この時点でaはupdateされている必要がある。
		//ループ中aはupdateせず、最後に1度だけupdateする
		if(isLocalRoot(a)) return;
		do {
			Node *q = a->parent;
			if(isLocalRoot(q)) {
				if(q->left == a) {
					rotateR(a);
					updateNode(a->right);
				}else {
					rotateL(a);
					updateNode(a->left);
				}
			}else {
				Node *r = q->parent;
				if(r->left == q) {
					if(q->left == a) {
						rotateR(q), rotateR(a);
						updateNode(q->right), updateNode(q);
					}else {
						rotateL(a), rotateR(a);
						updateNode(a->left), updateNode(a->right);
					}
				}else {
					if(q->right == a) {
						rotateL(q), rotateL(a);
						updateNode(q->left), updateNode(q);
					}else {
						rotateR(a), rotateL(a);
						updateNode(a->left), updateNode(a->right);
					}
				}
			}
		}while(!isLocalRoot(a));
		updateNode(a);
	}

	Node *newNode() {
		assert(!internalNodeFreeList.empty());
		Node *p = internalNodeFreeList.back(); internalNodeFreeList.pop_back();
		new(p) Node();

		return p;
	}
	void freeNode(Node *&a) {
		assert(getVertexIndex(a) == -1);

		a->left = a->right = a->parent = a->mid = reinterpret_cast<Node*>(0xdeaddead);
		internalNodeFreeList.push_back(a);
		a = NULL;
	}

	//global tree上での親ノードを取得する
	Node *globalParent(Node *a) {
		localSplay(a);
		return a->parent;
	}
	//globalParentと同じだがsplayせずに取得する
	Node *globalParentNoSplay(Node *a) {
		while(!isLocalRoot(a)) a = a->parent;
		return a->parent;
	}
	//global tree上での根ノードを取得する
	Node *getRootNode(int u) {
		Node *a = &vertexNodes[u];
		while(a->parent) a = globalParent(a);
		return a;
	}
	//aからrootへのパスを更新する
	void updatePath(Node *a) {
		while(a) {
			updateNode(a);
			localSplay(a);
			a = a->parent;
		}
	}

	//local tree上でaを削除する(切り離す)。aのglobal tree上の親を返す。cutNodeなどで内部的に用いるためのもの
	Node *deleteNode(Node *a) {
		localSplay(a);
		Node *r = a->left, *p = a->parent;
		if(!r) {
			if(r = a->right) r->parent = a->parent;
			if(a->parent) a->parent->mid = r;
		}else {
			while(r->right) r = r->right;
			localSplay(r);
			assert(r->right == a && !a->left);
			Node *b = a->right;
			if(r->right = b) b->parent = r;
			updateNode(r);
		}
		a->left = a->right = a->parent = NULL;
		updateNode(a);
		return p;
	}
	//global tree上でaから親への辺をカットする
	void cutNode(Node *a) {
		int numLeafs = a->numLeafs;
		Node *b = deleteNode(a);
		while(b) {
			updateNode(b);
			b->numLeafs -= numLeafs;
			b = globalParent(b);
		}
	}
	//aが子,bが親としてglobal tree上でリンクする
	void linkNode(Node *a, Node *b) {
		assert(!a->left && !a->right && !a->parent);
		int numLeafs = a->numLeafs;
		a->parent = b;
		if(a->left = b->mid) a->left->parent = a;
		b->mid = a;
		updateNode(a);
		while(b) {
			updateNode(b);
			b->numLeafs += numLeafs;
			b = globalParent(b);
		}
	}

	//local search treeをマージする
	//親がいないように切り離してからmergeする必要がある
	void mergeNode(Node *a, Node *b) {
		assert(!a->parent && !a->left && !a->right && !b->parent && !b->left && !b->right);
		Node *c = newNode();
		if(c->left = a->mid) c->left->parent = c;
		if(c->right = b->mid) c->right->parent = c;
		c->parent = a, a->mid = c;
		updateNode(c);
		updateNode(a);
		deleteNode(c);
		freeNode(c);
		b->mid = NULL;
		a->numLeafs += b->numLeafs;
		freeNode(b);
	}

	//レベルがちょうどlvになるように、ノードが省略されている場合は新たに作って返す
	Node *getLevelNode(Node *a, int lv) {
		if(a->level == lv) return a;
		Node *b = newNode();
		if(a->level > lv) {
			Node *p = a->parent;
			if(p) {
				if(p->left == a) p->left = b;
				else if(p->right == a) p->right = b;
				else p->mid = b;
			}
			b->parent = p;
			b->mid = a; a->parent = b;
			if(b->left = a->left) b->left->parent = b;
			if(b->right = a->right) b->right->parent = b;
			a->left = a->right = NULL;
			updateNode(a);
			updateNode(b);
			b->numLeafs = a->numLeafs;
			b->level = lv;
		}else {
			assert(false);
		}
		return b;
	}

	//aの子が1つだけだったら無駄なのでcontractする。下のノードを残すようにする
	Node *contractOneChildNode(Node *a) {
		Node *b = a->mid;
		if(!(b && !b->left && !b->right)) return a;
		Node *p = a->parent;
		b->parent = p;
		if(p) {
			if(p->left == a) p->left = b;
			else if(p->right == a) p->right = b;
			else p->mid = b;
		}
		if(b->left = a->left) b->left->parent = b;
		if(b->right = a->right) b->right->parent = b;
		updateNode(b);
		freeNode(a);
		return b;
	}

	//edgeからarcを取得する。arcは向きがあるので2つに対応する
	int arc1(int ei) const { return ei; }
	int arc2(int ei) const { return ei + numMaxEdges(); }
	//arcからedgeを取得する
	int arcEdge(int i) const { return i >= numMaxEdges() ? i - numMaxEdges() : i; }

	//vはarcのtail
	void insertArcToList(int i, int v) {
		int lv = edgeLevel[arcEdge(i)];
		bool treeEdge = isTreeEdge[arcEdge(i)];
		std::vector<int> &first = treeEdge ? firstTreeArc : firstNonTreeArc;

		int it = first[v], prev = -1;
		while(it != -1 && edgeLevel[arcEdge(it)] < lv) {
			prev = it;
			it = nextLevelArc[it];
		}

		prevPeerArc[i] = -1;
		if((prevLevelArc[i] = prev) != -1) nextLevelArc[prev] = i;
		else first[v] = i;

		int nextPeer = -1, nextLevel = -1;
		if(it != -1 && edgeLevel[arcEdge(it)] == lv) {
			nextPeer = it;
			nextLevel = nextLevelArc[it];
			nextLevelArc[it] = prevLevelArc[it] = -1;
		}else {
			nextLevel = it;
			std::vector<int> &levelEdges = treeEdge ? levelTreeEdges : levelNonTreeEdges;
			levelEdges[v] |= 1 << lv;
		}
		if((nextPeerArc[i] = nextPeer) != -1) prevPeerArc[nextPeer] = i;
		if((nextLevelArc[i] = nextLevel) != -1) prevLevelArc[nextLevel] = i;
	}
	void removeArcFromList(int i, int v) {
		int lv = edgeLevel[arcEdge(i)];
		bool treeEdge = isTreeEdge[arcEdge(i)];
		std::vector<int> &first = treeEdge ? firstTreeArc : firstNonTreeArc;

		int nextPeer = nextPeerArc[i], prevPeer = prevPeerArc[i];
		if(prevPeer != -1) nextPeerArc[prevPeer] = nextPeer;
		if(nextPeer != -1) prevPeerArc[nextPeer] = prevPeer;
		nextPeerArc[i] = prevPeerArc[i] = -2;

		if(prevPeer == -1) {
			int nextLevel = nextLevelArc[i], prevLevel = prevLevelArc[i];
			if(nextPeer != -1) {
				nextLevelArc[nextPeer] = nextLevel;
				prevLevelArc[nextPeer] = prevLevel;
				if(prevLevel != -1) nextLevelArc[prevLevel] = nextPeer;
				else first[v] = nextPeer;
				if(nextLevel != -1) prevLevelArc[nextLevel] = nextPeer;
			}else {
				if(prevLevel != -1) nextLevelArc[prevLevel] = nextLevel;
				else first[v] = nextLevel;
				if(nextLevel != -1) prevLevelArc[nextLevel] = prevLevel;

				std::vector<int> &levelEdges = treeEdge ? levelTreeEdges : levelNonTreeEdges;
				levelEdges[v] &= ~(1 << lv);
			}
		}else assert(nextLevelArc[i] == -1 && prevLevelArc[i] == -1);
		nextLevelArc[i] = prevLevelArc[i] = -2;
	}

	void insertEdgeToListNoUpdate(int ei) {
		insertArcToList(arc1(ei), arcHead[arc2(ei)]);
		insertArcToList(arc2(ei), arcHead[arc1(ei)]);
	}
	void removeEdgeFromListNoUpdate(int ei) {
		removeArcFromList(arc1(ei), arcHead[arc2(ei)]);
		removeArcFromList(arc2(ei), arcHead[arc1(ei)]);
	}
	void updateEdgeStatus(int ei) {
		updatePath(&vertexNodes[arcHead[arc1(ei)]]);
		updatePath(&vertexNodes[arcHead[arc2(ei)]]);
	}

	//このノードがvertex nodeである場合頂点番号を返す。そうでない場合-1を返す
	int getVertexIndex(const Node *a) const {
		const Node *first = &vertexNodes[0];
		if(first <= a && a < first + numVertices())
			return a - first;
		else
			return -1;
	}

	template<bool TreeEdge>
	inline int getFirstLevelArc(int v, int lv) {
		int it = TreeEdge ? firstTreeArc[v] : firstNonTreeArc[v];
		while(it != -1 && edgeLevel[arcEdge(it)] < lv)
			it = nextLevelArc[it];
		if(it == -1 || edgeLevel[arcEdge(it)] != lv) return -1;
		return it;
	}
	//根だけは左右(left,right)には行けない
	template<bool TreeEdge>
	inline void enumArcAddRoot(Node *a, int lv, std::vector<Node*> &stk, std::vector<int> &arcs) {
		int Node::*edgeBitset = TreeEdge ? &Node::treeEdges : &Node::nonTreeEdges;
		if(a->mid && (a->mid->*edgeBitset >> lv & 1))
			stk.push_back(a->mid);
		int v = getVertexIndex(a);
		if(v != -1) {
			int it = getFirstLevelArc<TreeEdge>(v, lv);
			if(it != -1) arcs.push_back(it);
		}
	}
	//enumArcNextがまだできるかどうか
	inline bool enumArcContinue(const std::vector<Node*> &stk, std::vector<int> &arcs) {
		return !stk.empty() || !arcs.empty();
	}
	//tree/nontree arcsを1つずつ列挙する
	template<bool TreeEdge>
	inline int enumArcNext(int lv, std::vector<Node*> &stk, std::vector<int> &arcs) {
		if(!arcs.empty()) {
			int currentArc = arcs.back();
			int next = nextPeerArc[currentArc];
			if(next == -1) arcs.pop_back();
			else arcs.back() = next;
			return currentArc;
		}
		int Node::*edgeBitset = TreeEdge ? &Node::treeEdges : &Node::nonTreeEdges;
		const std::vector<int> &levelEdges = TreeEdge ? levelTreeEdges : levelNonTreeEdges;
		int u;
		do {
			Node *a = stk.back(); stk.pop_back();
			assert(a->*edgeBitset >> lv & 1);
			if(a->left && (a->left->*edgeBitset >> lv & 1))
				stk.push_back(a->left);
			if(a->mid && (a->mid->*edgeBitset >> lv & 1))
				stk.push_back(a->mid);
			if(a->right && (a->right->*edgeBitset >> lv & 1))
				stk.push_back(a->right);
			u = getVertexIndex(a);
		}while(u == -1 || !(levelEdges[u] >> lv & 1));
		//この頂点から出てるレベルlvの木辺を列挙
		//木辺の次数がとても大きい頂点があるとone stepがboundしなくなってしまうので、遅延評価的にstateで保存しておく
		int it = getFirstLevelArc<TreeEdge>(u, lv);
		assert(it != -1);
		assert(edgeLevel[arcEdge(it)] == lv);
		arcs.push_back(it);
		return enumArcNext<TreeEdge>(lv, stk, arcs);
	}


	//global node aの木上で(v,w)を切った時に残る2つの木のうちサイズが小さいものを見つけ、
	//その側ua∈{va,wa}とそれに属するglobal tree中のaの子たちを返す
	Node *findSmallerTree(Node *a, Node *va, Node *wa, std::vector<Node*> &uNodes, std::vector<int> &uEdges, int &uSize) {
		int lv = a->level;
		int vsize = va->numLeafs, wsize = wa->numLeafs;
		std::vector<Node*> stkv, stkw, vNodes, wNodes;
		std::vector<int> vArcs, wArcs, vEdges, wEdges, xEdges;

		enumArcAddRoot<true>(va, lv, stkv, vArcs);
		enumArcAddRoot<true>(wa, lv, stkw, wArcs);
		while(enumArcContinue(stkv, vArcs) && enumArcContinue(stkw, wArcs)) {
			if(vsize <= wsize)
				vsize += findSmallerTreeStep(lv, stkv, vArcs, vNodes, vEdges);
			else
				wsize += findSmallerTreeStep(lv, stkw, wArcs, wNodes, wEdges);
		}
		for(int i = 0; i < (int)vEdges.size(); i ++)
			edgeVisited[vEdges[i]] = false;
		for(int i = 0; i < (int)wEdges.size(); i ++)
			edgeVisited[wEdges[i]] = false;

		Node *ua;
		if(!enumArcContinue(stkv, vArcs)) {
			ua = va, uSize = vsize, uNodes.swap(vNodes);
			uEdges.swap(vEdges), xEdges.swap(wEdges);
		}else {
			ua = wa, uSize = wsize, uNodes.swap(wNodes);
			uEdges.swap(wEdges), xEdges.swap(vEdges);
		}
		return ua;
	}

	inline int findSmallerTreeStep(int lv, std::vector<Node*> &stk, std::vector<int> &arcs, std::vector<Node*> &nodes, std::vector<int> &edges) {
		int i = enumArcNext<true>(lv, stk, arcs);
		int ei = arcEdge(i);
		if(edgeVisited[ei]) return 0;
		edgeVisited[ei] = true;
		edges.push_back(ei);
		Node *b = &vertexNodes[arcHead[i]];
		while(true) {
			Node *p = globalParent(b);	//探索してるとこをsplayすることはないはず
			if(p->level <= lv) break;
			b = p;
		}
		assert(lv < b->level);
		enumArcAddRoot<true>(b, lv, stk, arcs);	//向こう側も探索
		nodes.push_back(b);
		return b->numLeafs;
	}

	//aのsubtreeにincidentしてるレベルlvのnontree edgeを1つサンプルする
	//ランダムにサンプルってできないかと思うのだけど…とりあえずランダムさは無くやる。構造自体をランダムにするとか？
	int sampleNonTreeEdge(Node *a, int lv) {
		int v = getVertexIndex(a);
		if(v == -1) {
			Node *b = a->mid;
			if(!(b->nonTreeEdges >> lv & 1)) return -1;
			while(true) {
				v = getVertexIndex(b);
				if(v != -1 && (levelNonTreeEdges[v] >> lv & 1))
					break;
				if(b->left && (b->left->nonTreeEdges >> lv & 1))
					b = b->left;
				else if(b->right && (b->right->nonTreeEdges >> lv & 1))
					b = b->right;
				else if(b->mid && (b->mid->nonTreeEdges >> lv & 1))
					b = b->mid;
				else assert(false);
			}
		}
		return getFirstLevelArc<false>(v, lv);
	}

	//aのレベルでvとwを連結させる辺を見つける。見つかったかどうかを返す
	//va,waはv,wの祖先でglobal tree上でのaの子ノード
	bool replaceRec(int lv, Node *a, Node *va, Node *wa) {
		//小さい方の木T_uを見つける
		std::vector<Node*> uNodes; std::vector<int> uEdges; int uSize;
		Node *ua_t = findSmallerTree(a, va, wa, uNodes, uEdges, uSize);
		Node *ua = getLevelNode(ua_t, lv + 1);

		//T_uをglobal treeの構造的にレベルアップさせる
		cutNode(ua);
		for(int i = 0; i < (int)uNodes.size(); i ++) {
			Node *n = getLevelNode(uNodes[i], lv + 1);
			cutNode(n);
			mergeNode(ua, n);
		}
		//uaはcutしたままにしておく

		int replacementEdge = -1;
		std::vector<int> levelupEdges;
		//T_uのこのレベルのtree edgesをレベルアップさせるためにlevelupEdgesに入れとく
		levelupEdges.swap(uEdges);

		//まず何個かサンプリングする
		for(int k = 1; k <= uSize; k <<= 1) {
			int i = sampleNonTreeEdge(ua, lv);
			if(i == -1) break;
			int ei = arcEdge(i);
			//lvまで登る
			Node *b = &vertexNodes[arcHead[i]];
			while(b->parent && b->level > lv + 1) {
				b = globalParent(b);
			}
			if(b == ua) {
				//両端がT_u側にある辺である
				//サンプリングのために今ここでレベルアップする
				removeEdgeFromListNoUpdate(ei);
				edgeLevel[ei] ++;
				insertEdgeToListNoUpdate(ei);
				updateEdgeStatus(ei);
			}else {
				//replacement edgeが見つかった
				replacementEdge = ei;
				break;
			}
		}

		int treeEdgeCount = levelupEdges.size();
		//Test-All的な
		if(replacementEdge == -1) {
			//replacement edgeは少ないと仮定してやる

			std::vector<Node*> stk; static std::vector<int> arcs;
			stk.clear(); arcs.clear();
			//このレベルのT_uのnon tree edgesを列挙する
			enumArcAddRoot<false>(ua, lv, stk, arcs);
			while(enumArcContinue(stk, arcs)) {
				int i = enumArcNext<false>(lv, stk, arcs);
				int ei = arcEdge(i);
				vertexVisited[arcHead[i == arc1(ei) ? arc2(ei) : arc1(ei)]] = true;
				if(edgeVisited[ei]) continue;
				edgeVisited[ei] = true;

				levelupEdges.push_back(ei);
			}

			for(int i = treeEdgeCount; i < (int)levelupEdges.size(); i ++) {
				int ei = levelupEdges[i];
				if(!vertexVisited[arcHead[arc1(ei)]] || !vertexVisited[arcHead[arc2(ei)]]) {
					replacementEdge = ei;
					break;
				}
			}
		}
		for(int i = 0; i < (int)levelupEdges.size(); i ++) {
			int ei = levelupEdges[i];
			if(treeEdgeCount <= i) {
				//replacement edgeじゃないならTest-Allで両方の向きが見つかってるはず
				if(!vertexVisited[arcHead[arc1(ei)]] || !vertexVisited[arcHead[arc2(ei)]]) {
					//replacement edgeはレベルアップしない(できない)
					//replacement edgeばかりの時にlevel upできなくてpayできないので最初にサンプリングしてる
					if(replacementEdge == -1) {
						replacementEdge = ei;
					}
					continue;
				}
			}
			//見たedgeを実際にレベルアップさせる
			removeEdgeFromListNoUpdate(ei);
			edgeLevel[ei] ++;
			insertEdgeToListNoUpdate(ei);
			updateEdgeStatus(ei);
		}
		for(int i = treeEdgeCount; i < (int)levelupEdges.size(); i ++) {
			int ei = levelupEdges[i];
			edgeVisited[ei] = false;
			vertexVisited[arcHead[arc1(ei)]] = false;
			vertexVisited[arcHead[arc2(ei)]] = false;
		}
		if(replacementEdge != -1) {
			//replacement edgeが見つかった場合
			removeEdgeFromListNoUpdate(replacementEdge);
			isTreeEdge[replacementEdge] = true;
			insertEdgeToListNoUpdate(replacementEdge);
			updateEdgeStatus(replacementEdge);
			linkNode(ua, a);	//uaを連結させる
			a = contractOneChildNode(a);
			ua = contractOneChildNode(ua);
			edgeVisited[replacementEdge] = false;
			return true;
		}
		//replacement edgeが見つからなかった場合
		Node *up = newNode();
		up->level = lv;
		linkNode(ua, up);
		a = contractOneChildNode(a);
		up = contractOneChildNode(up);
		if(up == ua) up = ua = contractOneChildNode(ua);
		else ua = contractOneChildNode(ua);
		if(lv > 0) {
			Node *ap = globalParent(a);
			Node *p = ap && ap->level == lv-1 ? ap : getLevelNode(a, lv-1);
			linkNode(up, p);
			return replaceRec(lv-1, p, up, a);
		}else {
			return false;
		}
	}

	//aとbを連結させる辺を見つける。見つかったかどうかを返す
	bool replace(Node *a, Node *b) {
		//v,wのglobal tree上のlcaを見つける。ap,bpにそのすぐ下の子を保持しておく
		Node *ap = NULL, *bp = NULL;
		assert(a != b);
		while(a != b) {
			assert(a && b);
			if(a->level >= b->level)
				ap = a, a = globalParent(a);
			else if(a->level < b->level)
				bp = b, b = globalParent(b);
		}
		return replaceRec(a->level, a, ap, bp);
	}

	//コピコンはとりあえずdelete
	FullyDynamicConnectivity(const FullyDynamicConnectivity &that) { assert(false); }
	FullyDynamicConnectivity &operator=(const FullyDynamicConnectivity &that) { assert(false); }

public:
	FullyDynamicConnectivity() { }
	~FullyDynamicConnectivity() { }

	//floor(log_2(N))
	static int calcMaxLevel(int N) {
		int maxLevel = 0;
		while(1 << maxLevel <= N / 2) maxLevel ++;
		return maxLevel;
	}

	//頂点数N, 最大辺数Mとして初期化する(edgeless graphとなる)
	void init(int N, int M) {
		internalNodeFreeList.clear();
		//子を2つ以上まとめるノードになるには辺が必要。その他に一時的なノード分として＋α
		//よく考えてないのでだめかも。とにかくランダムケースではinternal nodeはとても少ない(だからテストが難しい)
		internalNodes.resize(M + 5);
		internalNodeFreeList.resize(internalNodes.size());
		for(int i = 0; i < (int)internalNodes.size(); i ++)
			internalNodeFreeList[i] = &internalNodes[i];

		int maxLevel = calcMaxLevel(N);

		vertexNodes.assign(N, Node());
		for(int i = 0; i < N; i ++) {
			vertexNodes[i].level = maxLevel;
			vertexNodes[i].numLeafs = 1;
		}
		
		isTreeEdge.assign(M, false);
		edgeLevel.assign(M, -1);

		arcHead.assign(M * 2, -1);

		levelTreeEdges.assign(N, 0);
		levelNonTreeEdges.assign(N, 0);

		firstTreeArc.assign(N, -1);
		firstNonTreeArc.assign(N, -1);

		nextLevelArc.assign(M * 2, -2);
		nextPeerArc.assign(M * 2, -2);
		prevLevelArc.assign(M * 2, -2);
		prevPeerArc.assign(M * 2, -2);

		edgeVisited.assign(M, false);
		vertexVisited.assign(N, false);
	}
	int numVertices() const { return vertexNodes.size(); }
	int numMaxEdges() const { return isTreeEdge.size(); }
	//uとvが連結しているかどうかを返す
	bool isConnected(int v, int w) {
		assert(0 <= v && v < numVertices() && 0 <= w && w < numVertices());
		return getRootNode(v) == getRootNode(w);
	}
	//vが属する連結成分のサイズを返す
	int getConnectedComponentSize(int v) {
		assert(0 <= v && v < numVertices());
		return getRootNode(v)->numLeafs;
	}
	//辺(u,v)を追加する。eiは辺のインデックスで、削除する時に指定する
	//connected componentsの数が減ったか(新たに連結されたか)を返す
	bool insertEdge(int ei, int v, int w) {
		assert(0 <= ei && ei < numMaxEdges() && 0 <= v && v < numVertices() && 0 <= w && w < numVertices());
		assert(edgeLevel[ei] == -1);

		Node *vRoot = getRootNode(v);
		Node *wRoot = getRootNode(w);
		bool treeEdge = vRoot != wRoot;

		isTreeEdge[ei] = treeEdge;
		edgeLevel[ei] = 0;

		int a1 = arc1(ei), a2 = arc2(ei);
		assert(arcHead[a1] == -1 && arcHead[a2] == -1);
		arcHead[a1] = w, arcHead[a2] = v;

		if(v != w) {	//ループは見たくないのでリストには登録しない
			insertEdgeToListNoUpdate(ei);
			updateEdgeStatus(ei);
		}

		if(treeEdge) {
			Node *v0 = getLevelNode(vRoot, 0), *w0 = getLevelNode(wRoot, 0);
			mergeNode(v0, w0);
		}
		return treeEdge;
	}
	//辺を削除する。eiは辺のインデックス
	//connected componentsの数が増えたか(新たに分離したか)を返す
	bool deleteEdge(int ei) {
		assert(0 <= ei && ei < numMaxEdges());
		assert(edgeLevel[ei] != -1);

		int a1 = arc1(ei), a2 = arc2(ei);
		int v = arcHead[a2], w = arcHead[a1];

		if(v != w) {	//ループは登録されていない
			removeEdgeFromListNoUpdate(ei);
			updateEdgeStatus(ei);
		}

		arcHead[a1] = arcHead[a2] = -1;

		bool treeEdge = isTreeEdge[ei];
		isTreeEdge[ei] = false;
		edgeLevel[ei] = -1;

		bool splited;
		if(!treeEdge) splited = false;
		else splited = !replace(&vertexNodes[v], &vertexNodes[w]);
		return splited;
	}
};

int main() {
	int N, M;
	scanf("%d%d", &N, &M);
	if((ll)N * (N-1) / 2 - M > N - 1) {
		rep(i, M) {
			int S, T;
			scanf("%d%d", &S, &T);
			puts("no");
		}
		return 0;
	}
	vector<vector<int> > edgeIndex(N);
	int totalEdges = 0;
	rep(i, N) {
		edgeIndex[i].resize(i);
		rep(j, i) edgeIndex[i][j] = totalEdges ++;
	}

	FullyDynamicConnectivity fdc;
	fdc.init(N, totalEdges);

	vector<bool> edgeExist(totalEdges);
	int numComponents = N, numEdges = 0;
	//最初に完全グラフにする
	rep(i, N) rep(j, i) {
		int ei = edgeIndex[i][j];
		numComponents -= fdc.insertEdge(ei, i, j);
		edgeExist[ei] = true;
		++ numEdges;
	}

	rep(i, M) {
		int S, T;
		scanf("%d%d", &S, &T), S --, T --;
		if(S < T) swap(S, T);
		int ei = edgeIndex[S][T];
		if(!edgeExist[ei]) {
			numComponents -= fdc.insertEdge(ei, S, T);
			edgeExist[ei] = true;
			++ numEdges;
		}else {
			numComponents += fdc.deleteEdge(ei);
			edgeExist[ei] = false;
			-- numEdges;
		}
//		cerr << "graph{"; rep(i, N) cerr << i << ";"; rep(i, N) rep(j, i) if(edgeExist[edgeIndex[i][j]]) cerr << i << "--" << j <<";"; cerr << "}" << endl;
//		cerr << N << " - " << numComponents << " == " << numEdges << endl;
		bool isForest = numEdges == N - numComponents;
		puts(isForest ? "yes" : "no");
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:794:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:798:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:825:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result