Submission #533782

---

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 HeavyLightDecomposition {
	vector<int> colors, positions;	//Vertex -> Color, Vertex -> Offset
	vector<int> lengths, parents, branches;	//Color -> Int, Color -> Color, Color -> Offset
	vector<int> parentnodes, depths;	//Vertex -> Vertex, Vertex -> Int
	//vector<FenwickTree>とかを避けて1次元にしたい時に使う
	//sortednodesの[lefts[v], rights[v])はvのsubtreeとなっている
	vector<int> sortednodes, offsets;	//Index -> Vertex, Color -> Index
	vector<int> lefts, rights;	//Vertex -> Index

	struct BuildDFSState {
		int i, len, parent;
		BuildDFSState() { }
		BuildDFSState(int i_, int l, int p): i(i_), len(l), parent(p) { }
	};

	//両方の辺があってもいいし、親から子への辺だけでもよい
	void build(const vector<vi> &g, int root) {
		int n = g.size();

		colors.assign(n, -1); positions.assign(n, -1);
		lengths.clear(); parents.clear(); branches.clear();
		parentnodes.assign(n, -1); depths.assign(n, -1);

		sortednodes.clear(); offsets.clear();
		lefts.assign(n, -1); rights.assign(n, -1);

		vector<int> subtreesizes;
		measure(g, root, subtreesizes);

		typedef BuildDFSState State;
		depths[root] = 0;
		vector<State> s;
		s.push_back(State(root, 0, -1));
		while(!s.empty()) {
			State t = s.back(); s.pop_back();
			int i = t.i, len = t.len;
			int index = sortednodes.size();
			int color = lengths.size();

			if(t.parent == -3) {
				rights[i] = index;
				continue;
			}

			if(t.parent != -2) {
				assert(parents.size() == color);
				parents.push_back(t.parent);
				branches.push_back(len);
				offsets.push_back(index);
				len = 0;
			}
			colors[i] = color;
			positions[i] = len;

			lefts[i] = index;
			sortednodes.push_back(i);

			int maxsize = -1, maxj = -1;
			each(j, g[i]) if(colors[*j] == -1) {
				if(maxsize < subtreesizes[*j]) {
					maxsize = subtreesizes[*j];
					maxj = *j;
				}
				parentnodes[*j] = i;
				depths[*j] = depths[i] + 1;
			}
			s.push_back(State(i, -1, -3));
			if(maxj == -1) {
				lengths.push_back(len + 1);
			}else {
				each(j, g[i]) if(colors[*j] == -1 && *j != maxj)
					s.push_back(State(*j, len, color));
				s.push_back(State(maxj, len + 1, -2));
			}
		}
	}
	
	void get(int v, int &c, int &p) const {
		c = colors[v]; p = positions[v];
	}
	bool go_up(int &c, int &p) const {
		p = branches[c]; c = parents[c];
		return c != -1;
	}

	inline const int *nodesBegin(int c) const { return &sortednodes[0] + offsets[c]; }
	inline const int *nodesEnd(int c) const { return &sortednodes[0] + (c+1 == offsets.size() ? sortednodes.size() : offsets[c+1]); }

private:
	void measure(const vector<vi> &g, int root, vector<int> &out_subtreesizes) const {
		out_subtreesizes.assign(g.size(), -1);
		vector<int> s;
		s.push_back(root);
		while(!s.empty()) {
			int i = s.back(); s.pop_back();
			if(out_subtreesizes[i] == -2) {
				int s = 1;
				each(j, g[i]) if(out_subtreesizes[*j] != -2)
					s += out_subtreesizes[*j];
				out_subtreesizes[i] = s;
			}else {
				s.push_back(i);
				each(j, g[i]) if(out_subtreesizes[*j] == -1)
					s.push_back(*j);
				out_subtreesizes[i] = -2;
			}
		}
	}
};

int lowest_common_ancestor(const HeavyLightDecomposition &hld, int x, int y) {
	int cx, px, cy, py;
	hld.get(x, cx, px);
	hld.get(y, cy, py);
	while(cx != cy) {
		if(hld.depths[*hld.nodesBegin(cx)] < hld.depths[*hld.nodesBegin(cy)])
			hld.go_up(cy, py);
		else
			hld.go_up(cx, px);
	}
	return hld.nodesBegin(cx)[min(px, py)];
}

void get_route(const HeavyLightDecomposition &hld, int u, int v, vector<pair<int,pii> > &route) {
	route.clear();
	int w = lowest_common_ancestor(hld, u, v), wc, wp;
	hld.get(w, wc, wp);
	rep(uv, 2) {
		int c, p;
		hld.get(uv == 0 ? u : v, c, p);
		int sz = route.size();
		while(1) {
			int top = c == wc ? wp + uv : 0;
			pii q = uv == 0 ? mp(p + 1, top) : mp(top, p + 1);
			if(q.first != q.second) {
				if(uv == 1 && c == wc) {	//cをユニークにするために
					assert(route[sz-1].first == c);
					assert(route[sz-1].second.first - route[sz-1].second.second == 1);
					assert(route[sz-1].second.first == q.first);
					route[sz-1].second = mp(route[sz-1].second.second, q.second);
				}else {
					route.push_back(mp(c, q));
				}
			}
			if(c == wc) break;
			hld.go_up(c, p);
		}
		if(uv == 1)
			reverse(route.begin() + sz, route.end());
	}
}


struct Node {
	static vector<Node> buf;
	static size_t bufp;
	typedef const Node *Ref;
	Ref l, r;
	int minPos, maxPos;
	Node(): l(NULL), r(NULL), minPos(INF), maxPos(-1) { }
	static Ref newNode(Ref l, Ref r, int minPos, int maxPos) {
		if(bufp == buf.size()) {
			cerr << "Memory exhausted!" << endl;
			abort();
		}
		Node *p = new(&buf[bufp ++])Node;
		p->l = l, p->r = r;
		p->minPos = minPos;
		p->maxPos = maxPos;
		return p;
	}
};
vector<Node> Node::buf;
size_t Node::bufp = 0;
typedef Node::Ref Ref;

Ref init(int left, int right) {
	if(left + 1 == right) {
		return Node::newNode(NULL, NULL, INF, -1);
	} else {
		int mid = (left + right) / 2;
		Ref l = init(left, mid);
		Ref r = init(mid, right);
		return Node::newNode(l, r, min(l->minPos, r->minPos), max(l->maxPos, r->maxPos));
	}
}

Ref insert(Ref p, int left, int right, int qi) {
	if(left + 1 == right) {
		assert(left == qi);
		return Node::newNode(NULL, NULL, qi, qi);
	} else {
		int mid = (left + right) / 2;
		Ref l = qi  < mid ? insert(p->l, left, mid, qi) : p->l;
		Ref r = mid <= qi ? insert(p->r, mid, right, qi) : p->r;
		return Node::newNode(l, r, min(l->minPos, r->minPos), max(l->maxPos, r->maxPos));
	}
}

int succ(Ref p, int left, int right, int ql, int qr) {
	if(ql <= left && right <= qr) {
		return p->minPos;
	} else {
		int mid = (left + right) / 2;
		int a = ql < mid ? succ(p->l, left, mid, ql, qr) : INF;
		int b = mid < qr ? succ(p->r, mid, right, ql, qr) : INF;
		return min(a, b);
	}
}

int pred(Ref p, int left, int right, int ql, int qr) {
	if(ql <= left && right <= qr) {
		return p->maxPos;
	} else {
		int mid = (left + right) / 2;
		int a = ql < mid ? pred(p->l, left, mid, ql, qr) : -1;
		int b = mid < qr ? pred(p->r, mid, right, ql, qr) : -1;
		return max(a, b);
	}
}

int main() {
	int n; int q;
	while(~scanf("%d%d", &n, &q)) {
		vector<int> a(n);
		for(int i = 0; i < n; ++ i)
			scanf("%d", &a[i]);
		vector<vi> g(n);
		rep(i, n - 1) {
			int b, c;
			scanf("%d%d", &b, &c), -- b, -- c;
			g[b].push_back(c);
			g[c].push_back(b);
		}
		HeavyLightDecomposition hld;
		hld.build(g, 0);
		vpii orda(n);
		rep(i, n) orda[i] = mp(a[i], i);
		sort(all(orda));
		Node::buf.resize(n * 20);
		Node::bufp = 0;
		Ref t = init(0, n);
		vector<Ref> ts(n+1);
		ts[0] = t;
		rep(ix, n) {
			int u = orda[ix].second, c, p;
			hld.get(u, c, p);
			int pos = hld.offsets[c] + p;
			t = insert(t, 0, n, pos);
			ts[ix + 1] = t;
		}
		vector<pair<int, pii> > route;
		rep(ii, q) {
			int x, u, v;
			scanf("%d%d%d", &x, &u, &v), -- u, -- v;
			get_route(hld, u, v, route);
			int curx = x;
			each(i, route) {
				int c = i->first, l = i->second.first, r = i->second.second;
				int o = hld.offsets[c];
				l += o, r += o;
				bool dir = l > r;
				if(dir) swap(l, r);
				while(l < r) {
					Ref t = ts[lower_bound(all(orda), mp(curx, INF)) - orda.begin()];
					int nextpos;
					if(!dir)
						nextpos = succ(t, 0, n, l, r);
					else
						nextpos = pred(t, 0, n, l, r);
					if(nextpos == -1 || nextpos == INF)
						break;
					int val = a[hld.sortednodes[nextpos]];
					assert(curx >= val);
					curx %= val;
					if(!dir)
						l = nextpos + 1;
					else
						r = nextpos;
				}
			}
			printf("%d\n", curx);
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:264:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i]);
                      ^
./Main.cpp:268:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &b, &c), -- b, -- c;
                                     ^
./Main.cpp:292:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &x, &u, &v), -- u, -- v;
                                           ^

Judge Result