Submission #372589

---

Source Code Expand

#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 <limits>
#include <functional>
#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;
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; }


struct Xor128 {
	unsigned x, y, z, w;
	Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { }
	unsigned next() {
		unsigned t = x ^ (x << 11);
		x = y; y = z; z = w;
		return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
	}
	//手抜き
	inline unsigned next(unsigned n) { return next() % n; }
};

//bottom upなTreap
//脱再帰！
//randomized binary searchにするにはchoiceRandomlyを
//	bool choiceRandomly(Ref l, Ref r) { return rng.next(l->size + r->size) < l->size; }
//に書き換えるだけでよい。
template<typename Node>
struct BottomupTreap {
	Xor128 rng;
	typedef Node *Ref;
	static int size(Ref t) { return !t ? 0 : t->size; }

	unsigned nextRand() { return rng.next(); }
private:
	bool choiceRandomly(Ref l, Ref r) {
		return l->priority < r->priority;
	}
public:

	Ref join(Ref l, Ref r) {
		if(!l) return r;
		if(!r) return l;

		Ref t = NULL;
		unsigned long long dirs = 0;
		int h;
		for(h = 0; ; ++ h) {
			if(h >= sizeof(dirs)*8 - 2) {
				//dirsのオーバーフローを防ぐために再帰する。
				//あくまでセーフティガードなのでバランスは多少崩れるかもしれない
				t = join(l->right, r->left);
				dirs = dirs << 2 | 1;
				h ++;
				break;
			}
			dirs <<= 1;
			if(choiceRandomly(l, r)) {
				Ref c = l->right;
				if(!c) {
					t = r;
					r = r->parent;
					break;
				}
				l = c;
			}else {
				dirs |= 1;
				Ref c = r->left;
				if(!c) {
					t = l;
					l = l->parent;
					break;
				}
				r = c;
			}
		}
		for(; h >= 0; -- h) {
			if(!(dirs & 1)) {
				Ref p = l->parent;
				t = l->linkr(t);
				l = p;
			}else {
				Ref p = r->parent;
				t = r->linkl(t);
				r = p;
			}
			dirs >>= 1;
		}
		return t;
	}

	typedef std::pair<Ref,Ref> RefPair;

	//l＜t≦rの(l,r)に分割する
	RefPair split2(Ref t) {
		Ref p, l = t->left, r = t;
		Node::cut(l); t->linkl(NULL);
		while(p = t->parent) {
			t->parent = NULL;
			if(p->left == t)
				r = p->linkl(r);
			else
				l = p->linkr(l);
			t = p;
		}
		return RefPair(l, r);
	}
	//l＜t＜rの(l,t,r)に分割する。(l,r)を返す
	RefPair split3(Ref t) {
		Ref p, l = t->left, r = t->right;
		Node::cut(l), Node::cut(r);
		t->linklr(NULL, NULL);
		while(p = t->parent) {
			t->parent = NULL;
			if(p->left == t)
				r = p->linkl(r);
			else
				l = p->linkr(l);
			t = p;
		}
		return RefPair(l, r);
	}
	Ref cons(Ref h, Ref t) {
		assert(size(h) == 1);
		if(!t) return h;
		Ref u = NULL;
		while(true) {
			if(choiceRandomly(h, t)) {
				Ref p = t->parent;
				u = h->linkr(t);
				t = p;
				break;
			}
			Ref l = t->left;
			if(!l) {
				u = h;
				break;
			}
			t = l;
		}
		while(t) {
			u = t->linkl(u);
			t = t->parent;
		}
		return u;
	}
};

class EulerTourTree {
	struct Node {
		typedef BottomupTreap<Node> BST;

		Node *left, *right, *parent;
		int size;
		unsigned priority;
		pair<int,int> val, mini;

		Node(): left(NULL), right(NULL), parent(NULL),
			size(1), priority(0), val(mp(INF, INF)), mini(mp(INF, INF)) { }

		inline Node *update() {
			int size_t = 1; pair<int,int> mini_t = val;
			if(left) {
				size_t += left->size;
				amin(mini_t, left->mini);
			}
			if(right) {
				size_t += right->size;
				amin(mini_t, right->mini);
			}
			size = size_t, mini = mini_t;
			return this;
		}

		inline Node *linkl(Node *c) {
			if(left = c) c->parent = this;
			return update();
		}
		inline Node *linkr(Node *c) {
			if(right = c) c->parent = this;
			return update();
		}
		inline Node *linklr(Node *l, Node *r) {
			if(left = l) l->parent = this;
			if(right = r) r->parent = this;
			return update();
		}
		static Node *cut(Node *t) {
			if(t) t->parent = NULL;
			return t;
		}

		static const Node *findRoot(const Node *t) {
			while(t->parent) t = t->parent;
			return t;
		}
		static std::pair<Node*,int> getPosition(Node *t) {
			int k = BST::size(t->left);
			Node *p;
			while(p = t->parent) {
				if(p->right == t)
					k += BST::size(p->left) + 1;
				t = p;
			}
			return std::make_pair(t, k);
		}
		static const Node *findHead(const Node *t) {
			while(t->left) t = t->left;
			return t;
		}
		static void updatePath(Node *t) {
			while(t) {
				t->update();
				t = t->parent;
			}
		}
	};

	typedef Node::BST BST;
	BST bst;

	std::vector<Node> nodes;
	//各頂点に対してその頂点から出ているarcを1つだけ代表として持つ(無い場合は-1)
	//逆にarcに対して対応する頂点はたかだか1つである
	std::vector<int> firstArc;

	inline int getArcIndex(const Node *a) const { return a - &nodes[0]; }

	inline int arc1(int ei) const { return ei; }
	inline int arc2(int ei) const { return ei + (numVertices() - 1); }

public:
	inline int numVertices() const { return firstArc.size(); }
	inline int numEdges() const { return numVertices() - 1; }
private:

	void updateMarks(int a, int v) {
		//nothing
	}

	//firstArcの変更に応じて更新する
	void firstArcChanged(int v, int a, int b) {
		if(a != -1) updateMarks(a, -1);
		if(b != -1) updateMarks(b, v);
	}

public:
	class TreeRef {
		friend class EulerTourTree;
		const Node *ref;
	public:
		TreeRef() { }
		TreeRef(const Node *ref_): ref(ref_) { }
		bool operator==(const TreeRef &that) const { return ref == that.ref; }
		bool operator!=(const TreeRef &that) const { return ref != that.ref; }
		bool isIsolatedVertex() const { return ref == NULL; }
	};

	void init(int N) {
		int M = N - 1;
		firstArc.assign(N, -1);
		nodes.assign(M * 2, Node());
		for(int i = 0; i < M * 2; i ++)
			nodes[i].priority = bst.nextRand();
	}

	TreeRef getTreeRef(int v) const {
		int a = firstArc[v];
		return TreeRef(a == -1 ? NULL : Node::findRoot(&nodes[a]));
	}

	bool isConnected(int v, int w) const {
		if(v == w) return true;
		int a = firstArc[v], b = firstArc[w];
		if(a == -1 || b == -1) return false;
		return Node::findRoot(&nodes[a]) == Node::findRoot(&nodes[b]);
	}

	int getTreeFirstArc(TreeRef t) const {
		assert(!t.isIsolatedVertex());
		return getArcIndex(t.ref);
	}

	static int getSize(TreeRef t) {
		if(t.isIsolatedVertex()) return 1;
		else return t.ref->size / 2 + 1;
	}

	static pair<int,int> getMini(TreeRef t) {
		assert(!t.isIsolatedVertex());
		return t.ref->mini;
	}

	void link(int ti, int v, int w) {
		int a1 = arc1(ti), a2 = arc2(ti);
		//v→wがa1に対応するようにする
		if(v > w) std::swap(a1, a2);

		int va = firstArc[v], wa = firstArc[w];

		Node *l, *m, *r;
		if(va != -1) {
			//evert。順番を入れ替えるだけ
			std::pair<Node*,Node*> p = bst.split2(&nodes[va]);
			m = bst.join(p.second, p.first);
		}else {
			//vが孤立点の場合
			m = NULL;
			firstArc[v] = a1;
			firstArcChanged(v, -1, a1);
		}
		if(wa != -1) {
			std::pair<Node*,Node*> p = bst.split2(&nodes[wa]);
			l = p.first, r = p.second;
		}else {
			//wが孤立点の場合
			l = r = NULL;
			firstArc[w] = a2;
			firstArcChanged(w, -1, a2);
		}
		//w→vの辺をmの先頭＝lの末尾にinsert
		m = bst.cons(&nodes[a2], m);
		//v→wの辺をmの末尾＝rの先頭にinsert
		r = bst.cons(&nodes[a1], r);

		bst.join(bst.join(l, m), r);
	}

	void cut(int ti, int v, int w) {
		//v→wがa1に対応するようにする
		if(v > w) std::swap(v, w);

		int a1 = arc1(ti), a2 = arc2(ti);
		std::pair<Node*,Node*> p = bst.split3(&nodes[a1]);
		int prsize = BST::size(p.second);
		std::pair<Node*,Node*> q = bst.split3(&nodes[a2]);
		Node *l, *m, *r;
		//a1,a2の順番を判定する。a1＜a2ならp.secondが変わっているはず
		if(p.second == &nodes[a2] || BST::size(p.second) != prsize) {
			l = p.first, m = q.first, r = q.second;
		}else {
			//a2＜a1の順番である。v→wの辺がa1であって親→子であることにする
			std::swap(v, w);
			std::swap(a1, a2);
			l = q.first, m = q.second, r = p.second;
		}

		//firstArcを必要に応じて書き換える
		if(firstArc[v] == a1) {
			int b;
			if(r != NULL) {
				//vが根じゃないなら右側の最初の辺でよい
				b = getArcIndex(Node::findHead(r));
			}else {
				//vが根なら最初の辺でよい。孤立点になるなら-1
				b = !l ? -1 : getArcIndex(Node::findHead(l));
			}
			firstArc[v] = b;
			firstArcChanged(v, a1, b);
		}
		if(firstArc[w] == a2) {
			//wが根になるので最初の辺でよい。孤立点になるなら-1
			int b = !m ? -1 : getArcIndex(Node::findHead(m));
			firstArc[w] = b;
			firstArcChanged(w, a2, b);
		}

		bst.join(l, r);
	}

	void changeEdgeValue(int ti, pair<int,int> x) {
		assert(ti < numEdges());
		Node *t = &nodes[ti];
		t->val = x;
		Node::updatePath(t);
	}

	pair<int,int> getEdgeValue(int ti) const {
		assert(ti < numEdges());
		const Node *t = &nodes[ti];
		return t->val;
	}
};

int main() {
	int N;
	scanf("%d", &N);
	vector<pii> edges(N-1);
	EulerTourTree ett; ett.init(N);
	rep(i, N-1) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c), -- a, -- b;
		edges[i] = mp(a, b);
		ett.changeEdgeValue(i, mp(c, i));
		ett.link(i, a, b);
	}
	vector<bool> deleted(N-1, false);
	int Q;
	scanf("%d", &Q);
	rep(ii, Q) {
		int ty;
		scanf("%d", &ty);
		if(ty == 1) {
			int i, d;
			scanf("%d%d", &i, &d), -- i;
			if(!deleted[i]) {
				pii p = ett.getEdgeValue(i);
				ett.changeEdgeValue(i, mp(p.first + d, p.second));
			}
		}else {
			int i;
			scanf("%d", &i), -- i;
			if(deleted[i]) {
				puts("-1");
			}else {
				EulerTourTree::TreeRef t = ett.getTreeRef(edges[i].first);
				assert(!t.isIsolatedVertex());
				pii p = ett.getMini(t);
				int j = p.second;
				printf("%d\n", j + 1);
				ett.cut(j, edges[j].first, edges[j].second);
				deleted[j] = true;
			}
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:415:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:420:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c), -- a, -- b;
                                          ^
./Main.cpp:427:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
./Main.cpp:430:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &ty);
                   ^
./Main.cpp:433:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &i, &d), ...

Judge Result