Ideone.com

fork download

copy

#include <bits/stdc++.h>
 
using namespace std;
 
namespace cartesian {
 
	struct node;
	typedef node* treap;
 
	struct node {
		node *l = 0, *r = 0, *p = 0;
		int64_t sum = 0, to_add = 0, val = 0;
		int to_nul = 0, siz = 1;
		int key, prior;
 
		node(int key, int val): sum(val), val(val), key(key), prior(rand()) {}
 
 
		#define safe(x, op) (x ? x->op : 0)
 
		treap fix() {
			safe(l, p = this);
			safe(r, p = this);
			sum = val + safe(l, sum) + safe(r, sum);
			siz = 1 + safe(l, siz) + safe(r, siz);
			return this;
		}
		treap cut_l() {
			push();
			safe(l, p = 0);
			return l;
		}
		treap cut_r() {
			push();
			safe(r, p = 0);
			return r;
		}
		treap set_l(treap x) {
			l = x;
			return fix();
		}
		treap set_r(treap x) {
			r = x;
			return fix();
		}
 
		treap nullify() {
			to_nul = 1;
			sum = to_add = val = 0;
			return this;
		}
		treap add(int64_t k) {
			to_add += k;
			val += k;
			sum += siz * k;
			return this;
		}
 
		treap push() {
			if(to_nul) {
				safe(l, nullify());
				safe(r, nullify());
				to_nul = 0;
			}
			if(to_add) {
				safe(l, add(to_add));
				safe(r, add(to_add));
				to_add = 0;
			}
			return this;
		}		
		treap root() {
			return p ? p->root() : this;
		}
		treap min() {
			return l ? l->min() : this;
		}
	};
	treap merge(treap a, treap b) {
		if(!a || !b) {
			return a ? a : b;
		} else if(a->prior < b->prior) {
			return a->set_r(merge(a->cut_r(), b));
		} else {
			return b->set_l(merge(a, b->cut_l()));
		}
	}
	pair<treap, treap> split(treap a, int k) {
		treap b, c;
		if(!a) {
			return {0, 0};
		} else if(a->key < k) {
			tie(b, c) = split(a->cut_r(), k);
			return {a->set_r(b), c};
		} else {
			tie(b, c) = split(a->cut_l(), k);
			return {b, a->set_l(c)};
		}
	}
	pair<treap, treap> cut(treap a, int l, int r) {
		treap b, c;
		tie(a, b) = split(a, l);
		tie(b, c) = split(b, r);
		return {merge(a, c), b};
	}
	treap link(treap a, treap x) {
		treap b;
		tie(a, b) = split(a, x->min()->key);
		return merge(a, merge(x, b));
	}
	pair<treap, treap> cut(treap x) {
		return cut(x->root(), x->key, x->key + 1);
	}
};
 
using namespace cartesian;
 
const int maxn = 5e5 + 42, logn = 22;
 
int sm[2][4 * maxn];
 
void add(int z, int p, int c, int v = 1, int l = 0, int r = maxn) {
	sm[z][v] += c;
	if(r - l > 1) {
		int m = (l + r) / 2;
		if(p < m) {
			add(z, p, c, 2 * v, l, m);
		} else {
			add(z, p, c, 2 * v + 1, m, r);
		}
	}
}
int sum(int p, int v = 1, int l = 0, int r = maxn) {
	if(r - l == 1) {
		return sm[0][v];
	} else {
		int m = (l + r) / 2;
		if(p < m) {
			return sum(p, 2 * v, l, m);
		} else {
			return (sm[0][2 * v] - sm[1][2 * v]) + sum(p, 2 * v + 1, m, r);
		}
	}
}
 
 
int to[maxn], a[maxn];
int in[maxn], out[maxn], rin[maxn];
int up[maxn][logn];
vector<int> g[maxn];
int sz, t;
string s;
 
treap nod[maxn];
 
 
int to_con;
set<int> non_zero;
 
int sum_root(int x) {
	return sum(out[x]);
}
void add_root(int x, int k) {
	add(0, in[x], k);
	add(1, out[x], k);
}
 
bool is_par(int a, int b) {
	return in[a] <= in[b] && out[b] <= out[a];
}
 
int lca(int a, int b) {
	for(int i = logn - 1; i >= 0; i--) {
		if(!is_par(up[a][i], b)) {
			a = up[a][i];
		}
	}
	if(!is_par(a, b)) {
		a = up[a][0];
	}
	return a;
}
 
int sum_path(int a, int b) {
	return sum_root(a) + sum_root(b) - 2 * sum_root(lca(a, b));
}
 
int process(int x) {
	if(non_zero.empty()) {
		return 0;
	} else {
		int g = lca(rin[*begin(non_zero)], rin[*prev(end(non_zero))]);
		if(is_par(g, x)) {
			vector<int> pos;
			int t = sum_root(x);
			auto it = non_zero.lower_bound(in[x]);
			if(it != end(non_zero)) {
				pos.push_back(t - sum_root(lca(x, rin[*it])));
			}
			if(it != begin(non_zero)) {
				pos.push_back(t - sum_root(lca(x, rin[*prev(it)])));
			}
			return *min_element(begin(pos), end(pos));
		} else {
			return sum_path(g, x);
		}
	}
}
void ins(int x) {
	to_con += process(x);
	non_zero.insert(in[x]);
}
void rem(int x) {
	non_zero.erase(in[x]);
	to_con -= process(x);
}
void upd(int x, int k) {
	auto it = non_zero.lower_bound(in[x]);
	auto jt = non_zero.lower_bound(out[x]);
	to_con += k * (it != jt && (it != begin(non_zero) || jt != end(non_zero)));
	add_root(x, k);
}
 
 
void dfs(int v = 0, int p = 0) {
	in[v] = t++;
	rin[in[v]] = v;
	nod[v] = new node(in[v], a[v]);
	for(auto it: g[v]) {
		int u = to[it];
		if(u != p) {
			up[u][0] = v;
			for(int i = 1; i < logn; i++) {
				up[u][i] = up[up[u][i - 1]][i - 1];
			}
			dfs(u, v);
			if(s[it / 2] == '0') {
				merge(nod[v]->root(), nod[u]->root());
			} else {
				upd(u, 1);
			}
		}
	}
	out[v] = t++;
}
 
void inv(int u, int v) {
	if(in[u] > in[v]) {
		swap(u, v);
	}
	auto U = nod[u]->root();
	auto V = nod[v]->root();
	if(U != V) {
		if(V->sum > 0) {
			rem(rin[V->min()->key]);
		}
		if(U->sum > 0) {
			rem(rin[U->min()->key]);
		}
		link(U, V);
		U = nod[u]->root();
		if(U->sum > 0) {
			ins(rin[U->min()->key]);
		}
		upd(v, -1);
	} else {
		if(U->sum > 0) {
			rem(rin[U->min()->key]);
		}
		cut(U, in[v], out[v]);
		U = nod[u]->root();
		V = nod[v]->root();
		if(U->sum > 0) {
			ins(rin[U->min()->key]);
		}
		if(V->sum > 0) {
			ins(rin[V->min()->key]);
		}
		upd(v, 1);
	}
}
void add(int x, int c) {
	if(nod[x]->root()->sum == 0 && c > 0) {
		ins(rin[nod[x]->root()->min()->key]);
	}
	nod[x]->root()->add(c);
}
void compose(int x) {
	treap a, b;
	tie(a, b) = cut(nod[x]);
	b->add(safe(a, sum));
	safe(a, nullify());
	link(a, b);
}
int64_t get(int x) {
	treap a, b;
	tie(a, b) = cut(nod[x]);
	int64_t res = b->sum;
	link(a, b);
	return res;
}
int64_t get_total(int x) {
	return nod[x]->root()->sum;
}
void full_nul(int x) {
	if(nod[x]->root()->sum > 0) {
		rem(rin[nod[x]->root()->min()->key]);
	}
	nod[x]->root()->nullify();
}
 
 
signed main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n;
	cin >> n >> m;
	int u[n], v[n];
	for(int i = 0; i < n - 1; i++) {
		cin >> u[i] >> v[i];
		u[i]--, v[i]--;
		g[v[i]].push_back(sz);
		to[sz++] = u[i];
		g[u[i]].push_back(sz);
		to[sz++] = v[i];
	}
	cin >> s;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	dfs();
	for(int x = 0; x < n; x++) {
		if(!nod[x]->p && nod[x]->sum != 0) {
			ins(rin[nod[x]->min()->key]);
		}
	}
	for(int i = 0; i < m; i++) {
		int t;
		cin >> t;
		if(t == 1) {
			int i;
			cin >> i;
			inv(u[i - 1], v[i - 1]);
		} else if(t == 2) {
			int x, c;
			cin >> x >> c;
			add(x - 1, c);
		} else if(t == 3) {
			int x;
			cin >> x;
			compose(x - 1);
		} else if(t == 4) {
			int x;
			cin >> x;
			cout << get(x - 1) << endl;
		} else if(t == 5) {
			int x;
			cin >> x;
			cout << get_total(x - 1) << endl;
		} else if(t == 6) {
			int x;
			cin >> x;
			full_nul(x - 1);
		} else {
			cout << to_con << endl;
		}
	}
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbmFtZXNwYWNlIGNhcnRlc2lhbiB7CgkKCXN0cnVjdCBub2RlOwoJdHlwZWRlZiBub2RlKiB0cmVhcDsKCQoJc3RydWN0IG5vZGUgewoJCW5vZGUgKmwgPSAwLCAqciA9IDAsICpwID0gMDsKCQlpbnQ2NF90IHN1bSA9IDAsIHRvX2FkZCA9IDAsIHZhbCA9IDA7CgkJaW50IHRvX251bCA9IDAsIHNpeiA9IDE7CgkJaW50IGtleSwgcHJpb3I7CgkJCgkJbm9kZShpbnQga2V5LCBpbnQgdmFsKTogc3VtKHZhbCksIHZhbCh2YWwpLCBrZXkoa2V5KSwgcHJpb3IocmFuZCgpKSB7fQoJCQoJCQoJCSNkZWZpbmUgc2FmZSh4LCBvcCkgKHggPyB4LT5vcCA6IDApCgkJCgkJdHJlYXAgZml4KCkgewoJCQlzYWZlKGwsIHAgPSB0aGlzKTsKCQkJc2FmZShyLCBwID0gdGhpcyk7CgkJCXN1bSA9IHZhbCArIHNhZmUobCwgc3VtKSArIHNhZmUociwgc3VtKTsKCQkJc2l6ID0gMSArIHNhZmUobCwgc2l6KSArIHNhZmUociwgc2l6KTsKCQkJcmV0dXJuIHRoaXM7CgkJfQoJCXRyZWFwIGN1dF9sKCkgewoJCQlwdXNoKCk7CgkJCXNhZmUobCwgcCA9IDApOwoJCQlyZXR1cm4gbDsKCQl9CgkJdHJlYXAgY3V0X3IoKSB7CgkJCXB1c2goKTsKCQkJc2FmZShyLCBwID0gMCk7CgkJCXJldHVybiByOwoJCX0KCQl0cmVhcCBzZXRfbCh0cmVhcCB4KSB7CgkJCWwgPSB4OwoJCQlyZXR1cm4gZml4KCk7CgkJfQoJCXRyZWFwIHNldF9yKHRyZWFwIHgpIHsKCQkJciA9IHg7CgkJCXJldHVybiBmaXgoKTsKCQl9CgkJCgkJdHJlYXAgbnVsbGlmeSgpIHsKCQkJdG9fbnVsID0gMTsKCQkJc3VtID0gdG9fYWRkID0gdmFsID0gMDsKCQkJcmV0dXJuIHRoaXM7CgkJfQoJCXRyZWFwIGFkZChpbnQ2NF90IGspIHsKCQkJdG9fYWRkICs9IGs7CgkJCXZhbCArPSBrOwoJCQlzdW0gKz0gc2l6ICogazsKCQkJcmV0dXJuIHRoaXM7CgkJfQoJCQoJCXRyZWFwIHB1c2goKSB7CgkJCWlmKHRvX251bCkgewoJCQkJc2FmZShsLCBudWxsaWZ5KCkpOwoJCQkJc2FmZShyLCBudWxsaWZ5KCkpOwoJCQkJdG9fbnVsID0gMDsKCQkJfQoJCQlpZih0b19hZGQpIHsKCQkJCXNhZmUobCwgYWRkKHRvX2FkZCkpOwoJCQkJc2FmZShyLCBhZGQodG9fYWRkKSk7CgkJCQl0b19hZGQgPSAwOwoJCQl9CgkJCXJldHVybiB0aGlzOwoJCX0JCQoJCXRyZWFwIHJvb3QoKSB7CgkJCXJldHVybiBwID8gcC0+cm9vdCgpIDogdGhpczsKCQl9CgkJdHJlYXAgbWluKCkgewoJCQlyZXR1cm4gbCA/IGwtPm1pbigpIDogdGhpczsKCQl9Cgl9OwoJdHJlYXAgbWVyZ2UodHJlYXAgYSwgdHJlYXAgYikgewoJCWlmKCFhIHx8ICFiKSB7CgkJCXJldHVybiBhID8gYSA6IGI7CgkJfSBlbHNlIGlmKGEtPnByaW9yIDwgYi0+cHJpb3IpIHsKCQkJcmV0dXJuIGEtPnNldF9yKG1lcmdlKGEtPmN1dF9yKCksIGIpKTsKCQl9IGVsc2UgewoJCQlyZXR1cm4gYi0+c2V0X2wobWVyZ2UoYSwgYi0+Y3V0X2woKSkpOwoJCX0KCX0KCXBhaXI8dHJlYXAsIHRyZWFwPiBzcGxpdCh0cmVhcCBhLCBpbnQgaykgewoJCXRyZWFwIGIsIGM7CgkJaWYoIWEpIHsKCQkJcmV0dXJuIHswLCAwfTsKCQl9IGVsc2UgaWYoYS0+a2V5IDwgaykgewoJCQl0aWUoYiwgYykgPSBzcGxpdChhLT5jdXRfcigpLCBrKTsKCQkJcmV0dXJuIHthLT5zZXRfcihiKSwgY307CgkJfSBlbHNlIHsKCQkJdGllKGIsIGMpID0gc3BsaXQoYS0+Y3V0X2woKSwgayk7CgkJCXJldHVybiB7YiwgYS0+c2V0X2woYyl9OwoJCX0KCX0KCXBhaXI8dHJlYXAsIHRyZWFwPiBjdXQodHJlYXAgYSwgaW50IGwsIGludCByKSB7CgkJdHJlYXAgYiwgYzsKCQl0aWUoYSwgYikgPSBzcGxpdChhLCBsKTsKCQl0aWUoYiwgYykgPSBzcGxpdChiLCByKTsKCQlyZXR1cm4ge21lcmdlKGEsIGMpLCBifTsKCX0KCXRyZWFwIGxpbmsodHJlYXAgYSwgdHJlYXAgeCkgewoJCXRyZWFwIGI7CgkJdGllKGEsIGIpID0gc3BsaXQoYSwgeC0+bWluKCktPmtleSk7CgkJcmV0dXJuIG1lcmdlKGEsIG1lcmdlKHgsIGIpKTsKCX0KCXBhaXI8dHJlYXAsIHRyZWFwPiBjdXQodHJlYXAgeCkgewoJCXJldHVybiBjdXQoeC0+cm9vdCgpLCB4LT5rZXksIHgtPmtleSArIDEpOwoJfQp9OwoKdXNpbmcgbmFtZXNwYWNlIGNhcnRlc2lhbjsKCmNvbnN0IGludCBtYXhuID0gNWU1ICsgNDIsIGxvZ24gPSAyMjsKCmludCBzbVsyXVs0ICogbWF4bl07Cgp2b2lkIGFkZChpbnQgeiwgaW50IHAsIGludCBjLCBpbnQgdiA9IDEsIGludCBsID0gMCwgaW50IHIgPSBtYXhuKSB7CglzbVt6XVt2XSArPSBjOwoJaWYociAtIGwgPiAxKSB7CgkJaW50IG0gPSAobCArIHIpIC8gMjsKCQlpZihwIDwgbSkgewoJCQlhZGQoeiwgcCwgYywgMiAqIHYsIGwsIG0pOwoJCX0gZWxzZSB7CgkJCWFkZCh6LCBwLCBjLCAyICogdiArIDEsIG0sIHIpOwoJCX0KCX0KfQppbnQgc3VtKGludCBwLCBpbnQgdiA9IDEsIGludCBsID0gMCwgaW50IHIgPSBtYXhuKSB7CglpZihyIC0gbCA9PSAxKSB7CgkJcmV0dXJuIHNtWzBdW3ZdOwoJfSBlbHNlIHsKCQlpbnQgbSA9IChsICsgcikgLyAyOwoJCWlmKHAgPCBtKSB7CgkJCXJldHVybiBzdW0ocCwgMiAqIHYsIGwsIG0pOwoJCX0gZWxzZSB7CgkJCXJldHVybiAoc21bMF1bMiAqIHZdIC0gc21bMV1bMiAqIHZdKSArIHN1bShwLCAyICogdiArIDEsIG0sIHIpOwoJCX0KCX0KfQoKCmludCB0b1ttYXhuXSwgYVttYXhuXTsKaW50IGluW21heG5dLCBvdXRbbWF4bl0sIHJpblttYXhuXTsKaW50IHVwW21heG5dW2xvZ25dOwp2ZWN0b3I8aW50PiBnW21heG5dOwppbnQgc3osIHQ7CnN0cmluZyBzOwoKdHJlYXAgbm9kW21heG5dOwoKCmludCB0b19jb247CnNldDxpbnQ+IG5vbl96ZXJvOwoKaW50IHN1bV9yb290KGludCB4KSB7CglyZXR1cm4gc3VtKG91dFt4XSk7Cn0Kdm9pZCBhZGRfcm9vdChpbnQgeCwgaW50IGspIHsKCWFkZCgwLCBpblt4XSwgayk7CglhZGQoMSwgb3V0W3hdLCBrKTsKfQoKYm9vbCBpc19wYXIoaW50IGEsIGludCBiKSB7CglyZXR1cm4gaW5bYV0gPD0gaW5bYl0gJiYgb3V0W2JdIDw9IG91dFthXTsKfQoKaW50IGxjYShpbnQgYSwgaW50IGIpIHsKCWZvcihpbnQgaSA9IGxvZ24gLSAxOyBpID49IDA7IGktLSkgewoJCWlmKCFpc19wYXIodXBbYV1baV0sIGIpKSB7CgkJCWEgPSB1cFthXVtpXTsKCQl9Cgl9CglpZighaXNfcGFyKGEsIGIpKSB7CgkJYSA9IHVwW2FdWzBdOwoJfQoJcmV0dXJuIGE7Cn0KCmludCBzdW1fcGF0aChpbnQgYSwgaW50IGIpIHsKCXJldHVybiBzdW1fcm9vdChhKSArIHN1bV9yb290KGIpIC0gMiAqIHN1bV9yb290KGxjYShhLCBiKSk7Cn0KCmludCBwcm9jZXNzKGludCB4KSB7CglpZihub25femVyby5lbXB0eSgpKSB7CgkJcmV0dXJuIDA7Cgl9IGVsc2UgewoJCWludCBnID0gbGNhKHJpblsqYmVnaW4obm9uX3plcm8pXSwgcmluWypwcmV2KGVuZChub25femVybykpXSk7CgkJaWYoaXNfcGFyKGcsIHgpKSB7CgkJCXZlY3RvcjxpbnQ+IHBvczsKCQkJaW50IHQgPSBzdW1fcm9vdCh4KTsKCQkJYXV0byBpdCA9IG5vbl96ZXJvLmxvd2VyX2JvdW5kKGluW3hdKTsKCQkJaWYoaXQgIT0gZW5kKG5vbl96ZXJvKSkgewoJCQkJcG9zLnB1c2hfYmFjayh0IC0gc3VtX3Jvb3QobGNhKHgsIHJpblsqaXRdKSkpOwoJCQl9CgkJCWlmKGl0ICE9IGJlZ2luKG5vbl96ZXJvKSkgewoJCQkJcG9zLnB1c2hfYmFjayh0IC0gc3VtX3Jvb3QobGNhKHgsIHJpblsqcHJldihpdCldKSkpOwoJCQl9CgkJCXJldHVybiAqbWluX2VsZW1lbnQoYmVnaW4ocG9zKSwgZW5kKHBvcykpOwoJCX0gZWxzZSB7CgkJCXJldHVybiBzdW1fcGF0aChnLCB4KTsKCQl9Cgl9Cn0Kdm9pZCBpbnMoaW50IHgpIHsKCXRvX2NvbiArPSBwcm9jZXNzKHgpOwoJbm9uX3plcm8uaW5zZXJ0KGluW3hdKTsKfQp2b2lkIHJlbShpbnQgeCkgewoJbm9uX3plcm8uZXJhc2UoaW5beF0pOwoJdG9fY29uIC09IHByb2Nlc3MoeCk7Cn0Kdm9pZCB1cGQoaW50IHgsIGludCBrKSB7CglhdXRvIGl0ID0gbm9uX3plcm8ubG93ZXJfYm91bmQoaW5beF0pOwoJYXV0byBqdCA9IG5vbl96ZXJvLmxvd2VyX2JvdW5kKG91dFt4XSk7Cgl0b19jb24gKz0gayAqIChpdCAhPSBqdCAmJiAoaXQgIT0gYmVnaW4obm9uX3plcm8pIHx8IGp0ICE9IGVuZChub25femVybykpKTsKCWFkZF9yb290KHgsIGspOwp9CgoKdm9pZCBkZnMoaW50IHYgPSAwLCBpbnQgcCA9IDApIHsKCWluW3ZdID0gdCsrOwoJcmluW2luW3ZdXSA9IHY7Cglub2Rbdl0gPSBuZXcgbm9kZShpblt2XSwgYVt2XSk7Cglmb3IoYXV0byBpdDogZ1t2XSkgewoJCWludCB1ID0gdG9baXRdOwoJCWlmKHUgIT0gcCkgewoJCQl1cFt1XVswXSA9IHY7CgkJCWZvcihpbnQgaSA9IDE7IGkgPCBsb2duOyBpKyspIHsKCQkJCXVwW3VdW2ldID0gdXBbdXBbdV1baSAtIDFdXVtpIC0gMV07CgkJCX0KCQkJZGZzKHUsIHYpOwoJCQlpZihzW2l0IC8gMl0gPT0gJzAnKSB7CgkJCQltZXJnZShub2Rbdl0tPnJvb3QoKSwgbm9kW3VdLT5yb290KCkpOwoJCQl9IGVsc2UgewoJCQkJdXBkKHUsIDEpOwoJCQl9CgkJfQoJfQoJb3V0W3ZdID0gdCsrOwp9Cgp2b2lkIGludihpbnQgdSwgaW50IHYpIHsKCWlmKGluW3VdID4gaW5bdl0pIHsKCQlzd2FwKHUsIHYpOwoJfQoJYXV0byBVID0gbm9kW3VdLT5yb290KCk7CglhdXRvIFYgPSBub2Rbdl0tPnJvb3QoKTsKCWlmKFUgIT0gVikgewoJCWlmKFYtPnN1bSA+IDApIHsKCQkJcmVtKHJpbltWLT5taW4oKS0+a2V5XSk7CgkJfQoJCWlmKFUtPnN1bSA+IDApIHsKCQkJcmVtKHJpbltVLT5taW4oKS0+a2V5XSk7CgkJfQoJCWxpbmsoVSwgVik7CgkJVSA9IG5vZFt1XS0+cm9vdCgpOwoJCWlmKFUtPnN1bSA+IDApIHsKCQkJaW5zKHJpbltVLT5taW4oKS0+a2V5XSk7CgkJfQoJCXVwZCh2LCAtMSk7Cgl9IGVsc2UgewoJCWlmKFUtPnN1bSA+IDApIHsKCQkJcmVtKHJpbltVLT5taW4oKS0+a2V5XSk7CgkJfQoJCWN1dChVLCBpblt2XSwgb3V0W3ZdKTsKCQlVID0gbm9kW3VdLT5yb290KCk7CgkJViA9IG5vZFt2XS0+cm9vdCgpOwoJCWlmKFUtPnN1bSA+IDApIHsKCQkJaW5zKHJpbltVLT5taW4oKS0+a2V5XSk7CgkJfQoJCWlmKFYtPnN1bSA+IDApIHsKCQkJaW5zKHJpbltWLT5taW4oKS0+a2V5XSk7CgkJfQoJCXVwZCh2LCAxKTsKCX0KfQp2b2lkIGFkZChpbnQgeCwgaW50IGMpIHsKCWlmKG5vZFt4XS0+cm9vdCgpLT5zdW0gPT0gMCAmJiBjID4gMCkgewoJCWlucyhyaW5bbm9kW3hdLT5yb290KCktPm1pbigpLT5rZXldKTsKCX0KCW5vZFt4XS0+cm9vdCgpLT5hZGQoYyk7Cn0Kdm9pZCBjb21wb3NlKGludCB4KSB7Cgl0cmVhcCBhLCBiOwoJdGllKGEsIGIpID0gY3V0KG5vZFt4XSk7CgliLT5hZGQoc2FmZShhLCBzdW0pKTsKCXNhZmUoYSwgbnVsbGlmeSgpKTsKCWxpbmsoYSwgYik7Cn0KaW50NjRfdCBnZXQoaW50IHgpIHsKCXRyZWFwIGEsIGI7Cgl0aWUoYSwgYikgPSBjdXQobm9kW3hdKTsKCWludDY0X3QgcmVzID0gYi0+c3VtOwoJbGluayhhLCBiKTsKCXJldHVybiByZXM7Cn0KaW50NjRfdCBnZXRfdG90YWwoaW50IHgpIHsKCXJldHVybiBub2RbeF0tPnJvb3QoKS0+c3VtOwp9CnZvaWQgZnVsbF9udWwoaW50IHgpIHsKCWlmKG5vZFt4XS0+cm9vdCgpLT5zdW0gPiAwKSB7CgkJcmVtKHJpbltub2RbeF0tPnJvb3QoKS0+bWluKCktPmtleV0pOwoJfQoJbm9kW3hdLT5yb290KCktPm51bGxpZnkoKTsKfQoKCnNpZ25lZCBtYWluKCkgewoJLy9mcmVvcGVuKCJpbnB1dC50eHQiLCAiciIsIHN0ZGluKTsKCWlvczo6c3luY193aXRoX3N0ZGlvKDApOwoJY2luLnRpZSgwKTsKCWludCBuLCBtOwoJY2luID4+IG47CgljaW4gPj4gbiA+PiBtOwoJaW50IHVbbl0sIHZbbl07Cglmb3IoaW50IGkgPSAwOyBpIDwgbiAtIDE7IGkrKykgewoJCWNpbiA+PiB1W2ldID4+IHZbaV07CgkJdVtpXS0tLCB2W2ldLS07CgkJZ1t2W2ldXS5wdXNoX2JhY2soc3opOwoJCXRvW3N6KytdID0gdVtpXTsKCQlnW3VbaV1dLnB1c2hfYmFjayhzeik7CgkJdG9bc3orK10gPSB2W2ldOwoJfQoJY2luID4+IHM7Cglmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJY2luID4+IGFbaV07Cgl9CglkZnMoKTsKCWZvcihpbnQgeCA9IDA7IHggPCBuOyB4KyspIHsKCQlpZighbm9kW3hdLT5wICYmIG5vZFt4XS0+c3VtICE9IDApIHsKCQkJaW5zKHJpbltub2RbeF0tPm1pbigpLT5rZXldKTsKCQl9Cgl9Cglmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CgkJaW50IHQ7CgkJY2luID4+IHQ7CgkJaWYodCA9PSAxKSB7CgkJCWludCBpOwoJCQljaW4gPj4gaTsKCQkJaW52KHVbaSAtIDFdLCB2W2kgLSAxXSk7CgkJfSBlbHNlIGlmKHQgPT0gMikgewoJCQlpbnQgeCwgYzsKCQkJY2luID4+IHggPj4gYzsKCQkJYWRkKHggLSAxLCBjKTsKCQl9IGVsc2UgaWYodCA9PSAzKSB7CgkJCWludCB4OwoJCQljaW4gPj4geDsKCQkJY29tcG9zZSh4IC0gMSk7CgkJfSBlbHNlIGlmKHQgPT0gNCkgewoJCQlpbnQgeDsKCQkJY2luID4+IHg7CgkJCWNvdXQgPDwgZ2V0KHggLSAxKSA8PCBlbmRsOwoJCX0gZWxzZSBpZih0ID09IDUpIHsKCQkJaW50IHg7CgkJCWNpbiA+PiB4OwoJCQljb3V0IDw8IGdldF90b3RhbCh4IC0gMSkgPDwgZW5kbDsKCQl9IGVsc2UgaWYodCA9PSA2KSB7CgkJCWludCB4OwoJCQljaW4gPj4geDsKCQkJZnVsbF9udWwoeCAtIDEpOwoJCX0gZWxzZSB7CgkJCWNvdXQgPDwgdG9fY29uIDw8IGVuZGw7CgkJfQoJfQoJcmV0dXJuIDA7Cn0K

Runtime error #stdin #stdout 0.02s 99264KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/mKfUan

language:

C++14 (gcc 8.3)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language