結果

問題 No.363 門松サイクル
ユーザー antaanta
提出日時 2016-04-20 17:59:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 92 ms / 4,000 ms
コード長 12,588 bytes
コンパイル時間 1,388 ms
コンパイル使用メモリ 111,688 KB
実行使用メモリ 28,312 KB
最終ジャッジ日時 2024-04-15 03:53:59
合計ジャッジ時間 3,856 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 3 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 28 ms
11,776 KB
testcase_10 AC 31 ms
12,032 KB
testcase_11 AC 62 ms
21,848 KB
testcase_12 AC 68 ms
21,852 KB
testcase_13 AC 68 ms
18,496 KB
testcase_14 AC 58 ms
17,160 KB
testcase_15 AC 56 ms
20,376 KB
testcase_16 AC 40 ms
16,896 KB
testcase_17 AC 77 ms
28,312 KB
testcase_18 AC 92 ms
19,984 KB
testcase_19 AC 78 ms
20,576 KB
testcase_20 AC 91 ms
20,036 KB
testcase_21 AC 86 ms
26,280 KB
testcase_22 AC 77 ms
19,764 KB
testcase_23 AC 60 ms
23,404 KB
testcase_24 AC 1 ms
6,944 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 48 ms
27,776 KB
testcase_27 AC 47 ms
27,764 KB
testcase_28 AC 61 ms
24,724 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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; }


class FastInput {
	bool _end;
public:
	FastInput() : _end(false) {}

	operator void*() { return _end ? 0 : (void*)this; }

	template<typename T>
	void read_unsigned(T *res) {
		T x = 0;
		for(char c = skip(); '0' <= c && c <= '9'; c = gc())
			x = x * 10 + (c - '0');
		*res = x;
	}

	template<typename T>
	void read_signed(T *res) {
		char c = skip();
		bool sign = false;
		if(c == '-') sign = true, c = gc();
		T x = 0;
		for(; '0' <= c && c <= '9'; c = gc())
			x = x * 10 + (c - '0');
		*res = !sign ? x : -x;
	}

	void read_c_string(char *str, int *len) {
		int n = 0;
		for(char c = skip(); !is_delim(c); c = gc())
			str[n ++] = c;
		str[n] = 0;
		*len = n;
	}

	void read_string(std::string *str) {
		str->clear();
		for(char c = skip(); !is_delim(c); c = gc())
			*str += c;
	}

	void read_line(std::string *str) {
		str->clear();
		for(char c = gc(); c != '\n'; c = gc())
			*str += c;
		if(!str->empty() && (*str)[str->size() - 1] == '\r') str->resize(str->size() - 1);
	}

	void read_double(double *res) {
		std::string buf;
		read_string(&buf);
		sscanf(buf.c_str(), "%lf", res);
	}

	void read_char(char *res) {
		*res = skip();
	}

	void read_string_buf(char *res, int n) {
		*res = skip();
	}

	FastInput &operator()(char &res) { read_char(&res); return *this; }
	FastInput &operator()(int &res) { read_signed(&res); return *this; }
	FastInput &operator()(unsigned &res) { read_unsigned(&res); return *this; }
	FastInput &operator()(long long &res) { read_signed(&res); return *this; }
	FastInput &operator()(unsigned long long &res) { read_unsigned(&res); return *this; }
	FastInput &operator()(char *res) { int len; read_c_string(res, &len); return *this; }
	FastInput &operator()(std::string &res) { read_string(&res); return *this; }
	FastInput &operator()(double &res) { read_double(&res); return *this; }

	template<typename T1, typename T2>
	FastInput &operator()(T1 &res1, T2 &res2) {
		return operator()(res1)(res2);
	}
	template<typename T1, typename T2, typename T3>
	FastInput &operator()(T1 &res1, T2 &res2, T3 &res3) {
		return operator()(res1)(res2)(res3);
	}

	template<typename T>
	FastInput &a(T *a, int n) {
		for(int i = 0; i < n; ++ i)
			operator()(a[i]);
		return *this;
	}

	template<typename T>
	FastInput &operator()(vector<T> &v) {
		for(size_t i = 0; i < v.size(); ++ i)
			operator()(v[i]);
		return *this;
	}

private:
	static char gc() {
#if defined(__GNUC__) && !defined(__MINGW32__)
		return (char)getchar_unlocked();
#elif defined(_MSC_VER)
		return (char)_getchar_nolock();
#else
		return (char)getchar();
#endif
	}

	static bool is_delim(char c) {
		return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == EOF;
	}

	char skip() {
		if(_end) return EOF;
		char c;
		for(c = gc(); c != -1 && is_delim(c); c = gc());
		if(c == EOF) _end = true;
		return c;
	}
} in;

class FastOutput {
public:

	template<typename T>
	void print_unsigned(T x) {
		char buf[24]; int n = 0;
		do buf[n ++] = x % 10, x /= 10; while(x != 0);
		while(n > 0) pc('0' + buf[-- n]);
	}

	template<typename T>
	void print_signed(T x) {
		char buf[24]; int n = 0; bool sign = false;
		if(x < 0) sign = true;
		//depends on the -x % y behaviour
		do buf[n ++] = x % 10, x /= 10; while(x != 0);
		if(!sign) {
			while(n > 0) pc('0' + buf[-- n]);
		} else {
			pc('-');
			while(n > 0) pc('0' - buf[-- n]);
		}
	}

	void print_c_string(const char *str) {
		for(const char *p = str; *p; ++ p)
			pc(*p);
	}

	void print_string(const std::string &str) {
		print_c_string(str.c_str());
	}

	void print_double(double x, int digits) {
		//|res| < 2^1024 ~ 10^308
		char buf[512];
#ifdef _MSC_VER
		sprintf_s(buf, "%.*f", digits, x);
#else
		sprintf(buf, "%.*f", digits, x);
#endif
		print_c_string(buf);
	}

	void print_char(char x) {
		pc(x);
	}

	FastOutput &operator()(char x) { print_char(x); return *this; }
	FastOutput &operator()(int x) { print_signed(x); return *this; }
	FastOutput &operator()(unsigned x) { print_unsigned(x); return *this; }
	FastOutput &operator()(long long x) { print_signed(x); return *this; }
	FastOutput &operator()(unsigned long long x) { print_unsigned(x); return *this; }
	FastOutput &operator()(const char *str) { print_c_string(str); return *this; }
	FastOutput &operator()(const std::string &str) { print_string(str); return *this; }
	FastOutput &operator()(double x) { print_double(x, 10); return *this; }

	template<typename T1, typename T2>
	FastOutput &operator()(T1 x1, T2 x2) { return operator()(x1)(x2); }
	template<typename T1, typename T2, typename T3>
	FastOutput &operator()(T1 x1, T2 x2, T3 x3) { return operator()(x1)(x2)(x3); }
	template<typename T1, typename T2, typename T3, typename T4>
	FastOutput &operator()(T1 x1, T2 x2, T3 x3, T4 x4) { return operator()(x1)(x2)(x3)(x4); }

private:
	static void pc(char c) {
#if defined(__GNUC__) && !defined(__MINGW32__)
		putchar_unlocked(c);
#elif defined(_MSC_VER)
		_putchar_nolock(c);
#else
		putchar(c);
#endif
	}
} out;

class FastOutputN {
public:
	template<typename T1>
	FastOutputN &operator()(T1 x1) { out(x1)('\n'); return *this; }
	template<typename T1, typename T2>
	FastOutputN &operator()(T1 x1, T2 x2) { out(x1, x2)('\n'); return *this; }
	template<typename T1, typename T2, typename T3>
	FastOutputN &operator()(T1 x1, T2 x2, T3 x3) { out(x1, x2, x3)('\n'); return *this; }
	template<typename T1, typename T2, typename T3, typename T4>
	FastOutputN &operator()(T1 x1, T2 x2, T3 x3, T4 x4) { out(x1, x2, x3, x4)('\n'); return *this; }

	template<typename T>
	FastOutputN &a(const T *a, int n) {
		for(int i = 0; i < n; ++ i) {
			if(i != 0) out(' ');
			out(a[i]);
		}
		out('\n');
		return *this;
	}

	template<typename T>
	FastOutputN &operator()(const vector<T> &v) {
		for(size_t i = 0; i < v.size(); ++ i) {
			if(i != 0) out(' ');
			out(v[i]);
		}
		out('\n');
		return *this;
	}
} outn;

class SchieberVishkinLCA {
public:
	typedef unsigned Word;
	typedef int Vertex;
private:

	static inline Word lowestOneBit(Word v) {
		return v & (~v + 1);
	}
	static inline Word highestOneBitMask(Word v) {
		v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;
		return v >> 1;
	}

	std::vector<Word> indices;			//Vertex -> index
	std::vector<Word> maxHIndices;		//Vertex -> index
	std::vector<Word> ancestorHeights;	//Vertex -> Word
	std::vector<Vertex> pathParents;	//index-1 -> Vertex
public:

	void build(const std::vector<Vertex> &preorder, const std::vector<Vertex> &parents, Vertex root) {
		Vertex N = static_cast<Vertex>(preorder.size());

		ancestorHeights.resize(N);
		maxHIndices.resize(N);
		indices.resize(N);
		pathParents.resize(N);

		for(Vertex ix = 0; ix < N; ++ ix)
			indices[preorder[ix]] = ix + 1;

		for(Vertex i = 0; i < N; ++ i)
			maxHIndices[i] = indices[i];
		for(Vertex ix = N - 1; ix > 0; -- ix) {
			Vertex v = preorder[ix], parent = parents[v];
			if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v]))
				maxHIndices[parent] = maxHIndices[v];
		}

		ancestorHeights[root] = 0;
		for(Vertex ix = 1; ix < N; ++ ix) {
			Vertex v = preorder[ix], parent = parents[v];
			ancestorHeights[v] = ancestorHeights[parent] | lowestOneBit(maxHIndices[v]);
		}

		pathParents[0] = root;
		for(Vertex ix = 1; ix < N; ++ ix) {
			Vertex v = preorder[ix], parent = parents[v];
			if(maxHIndices[v] != maxHIndices[parent])
				pathParents[indices[v] - 1] = parent;
			else
				pathParents[indices[v] - 1] = pathParents[indices[parent] - 1];
		}
	}

	Vertex query(Vertex v, Vertex u) const {
		Word Iv = maxHIndices[v], Iu = maxHIndices[u];
		Word hIv = lowestOneBit(Iv), hIu = lowestOneBit(Iu);
		Word hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu);
		Word j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);
		Vertex x, y;
		if(j == hIv) x = v;
		else {
			Word kMask = highestOneBitMask(ancestorHeights[v] & (j - 1));
			x = pathParents[(indices[v] & ~kMask | (kMask + 1)) - 1];
		}
		if(j == hIu) y = u;
		else {
			Word kMask = highestOneBitMask(ancestorHeights[u] & (j - 1));
			y = pathParents[(indices[u] & ~kMask | (kMask + 1)) - 1];
		}
		return indices[x] < indices[y] ? x : y;
	}
};

vector<int> t_parent;
vi t_ord;

void tree_getorder(const vector<vi> &g, int root) {
	int n = g.size();
	t_parent.assign(n, -1);
	t_ord.clear();

	vector<int> stk; stk.push_back(root);
	while(!stk.empty()) {
		int i = stk.back(); stk.pop_back();
		t_ord.push_back(i);
		for(int j = (int)g[i].size() - 1; j >= 0; j --) {
			int c = g[i][j];
			if(t_parent[c] == -1 && c != root)
				stk.push_back(c);
			else
				t_parent[i] = c;
		}
	}
}


bool isok(int a, int b, int c) {
	return a != c && ((a < b && b > c) || (a > b && b < c));
}

struct LevelAncestorQuery {
	int depth, i;
};

void batchedLevelAncestorQueries(int i, int p, const vector<vi> &g, vi &path, const vector<vector<LevelAncestorQuery>> &queries, vector<int> &res) {
	path.push_back(i);
	for(const LevelAncestorQuery &q : queries[i])
		res[q.i] = (int)path.size() <= q.depth ? -1 : path[q.depth];
	for(int j : g[i]) if(j != p)
		batchedLevelAncestorQueries(j, i, g, path, queries, res);
	path.pop_back();
}

int main() {
	int N;
	while(in(N)) {
		vector<int> A(N);
		in(A);
		vector<vector<int> > g(N);
		for(int i = 0; i < N - 1; ++ i) {
			int u, v;
			in(u, v), -- u, -- v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		tree_getorder(g, 0);
		vector<bool> parok(N);
		for(int ix = 0; ix < (int)t_ord.size(); ++ ix) {
			int i = t_ord[ix], p = t_parent[i];
			parok[i] = p == -1 || p == 0 || isok(A[t_parent[p]], A[p], A[i]);
		}
		vector<int> okcnt(N), depth(N);
		okcnt[0] = 1;
		for(int ix = 1; ix < (int)t_ord.size(); ++ ix) {
			int i = t_ord[ix], p = t_parent[i];
			okcnt[i] = okcnt[p] + parok[i];
			depth[i] = depth[p] + 1;
		}
		SchieberVishkinLCA lca;
		lca.build(t_ord, t_parent, 0);
		int Q;
		in(Q);
		vector<pair<int, int>> queries(Q);
		vector<int> ws(Q);
		vector<vector<LevelAncestorQuery>> laqueries(N);
		rep(qi, Q) {
			int u; int v;
			in(u, v), -- u, -- v;
			queries[qi] = { u, v };
		}
		vector<bool> ans(Q, true);
		rep(qi, Q) {
			int u, v; tie(u, v) = queries[qi];
			int w = lca.query(u, v);
			ws[qi] = w;
			int len = depth[u] + depth[v] - depth[w] * 2 + 1;
			if(len <= 2) {
				ans[qi] = false;
			} else {
				if(u != w)
					laqueries[u].push_back(LevelAncestorQuery{ depth[w] + 1, qi * 2 + 0 });
				if(v != w)
					laqueries[v].push_back(LevelAncestorQuery{ depth[w] + 1, qi * 2 + 1 });
			}
		}
		vector<int> cs(Q * 2, -1);
		{
			vector<int> path;
			batchedLevelAncestorQueries(0, -1, g, path, laqueries, cs);
		}
		rep(qi, Q) {
			if(ans[qi]) {
				int u, v; tie(u, v) = queries[qi];
				int w = ws[qi];
				int num = 0;
				int cu = cs[qi * 2 + 0], cv = cs[qi * 2 + 1];
				//wが真ん中
				if(w != u && w != v) {
					ans[qi] = ans[qi] && isok(A[cu], A[w], A[cv]);
					num += 1;
				}
				//u～w, v～w
				rep(uv, 2) {
					int t = uv == 0 ? u : v, a = uv == 0 ? cu : cv;
					if(t == w) continue;
					ans[qi] = ans[qi] && okcnt[t] - okcnt[a] == depth[t] - depth[a];
					num += depth[t] - depth[a];
				}
				//追加された辺を含むもの
				rep(uv, 2) {
					int x = uv == 0 ? u : v, y = uv == 0 ? v : u;
					int c;
					if(y == w) {
						c = uv == 0 ? cu : cv;
					} else {
						c = t_parent[y];
					}
					ans[qi] = ans[qi] && isok(A[x], A[y], A[c]);
					num += 1;
				}
				assert(num == depth[u] + depth[v] - depth[w] * 2 + 1);
			}
			outn(ans[qi] ? "YES" : "NO");
		}
	}
	return 0;
}
0