結果

問題 No.363 門松サイクル
ユーザー btkbtk
提出日時 2016-05-24 14:50:13
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 296 ms / 4,000 ms
コード長 3,109 bytes
コンパイル時間 1,781 ms
コンパイル使用メモリ 174,816 KB
実行使用メモリ 32,776 KB
最終ジャッジ日時 2023-08-01 13:23:52
合計ジャッジ時間 9,365 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 5 ms
4,380 KB
testcase_03 AC 3 ms
4,376 KB
testcase_04 AC 5 ms
4,376 KB
testcase_05 AC 4 ms
4,380 KB
testcase_06 AC 5 ms
4,376 KB
testcase_07 AC 4 ms
4,376 KB
testcase_08 AC 5 ms
4,376 KB
testcase_09 AC 111 ms
12,612 KB
testcase_10 AC 115 ms
13,188 KB
testcase_11 AC 203 ms
26,008 KB
testcase_12 AC 273 ms
24,060 KB
testcase_13 AC 253 ms
20,384 KB
testcase_14 AC 210 ms
18,800 KB
testcase_15 AC 183 ms
24,536 KB
testcase_16 AC 157 ms
18,984 KB
testcase_17 AC 263 ms
32,776 KB
testcase_18 AC 296 ms
22,216 KB
testcase_19 AC 247 ms
22,836 KB
testcase_20 AC 284 ms
22,316 KB
testcase_21 AC 277 ms
29,976 KB
testcase_22 AC 290 ms
21,788 KB
testcase_23 AC 254 ms
26,108 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 2 ms
4,380 KB
testcase_26 AC 222 ms
32,724 KB
testcase_27 AC 226 ms
32,716 KB
testcase_28 AC 295 ms
27,232 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
* Problem link
* http://yukicoder.me/problems/1024
*/

/*門松を許すな！！！！！！！！！！！！！！！！！！！！！*/

#include<bits/stdc++.h>
using namespace std;

struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init;

#define rep(i,n) for(auto i=(n)*0;i<n;i++)
#define range(it,v) for(auto &it:v)
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<int> E;
typedef vector<E> Graph;
bool checkKadomatsu(int a, int b, int c) {
	return (a != c) ? ((a > b&&b < c) || (a<b&&b>c)) : false;
}
void make_tree(int v, Graph &G, VV &PP, V &D, V &A, V &prev, V& len) {
	range(u, G[v]) {
		if (u != PP[0][v]) {
			D[u] = D[v] + 1;
			PP[0][u] = v;
			prev[u] = A[v];
			if (checkKadomatsu(prev[v],A[v],A[u]))
				len[u] = len[v] + 1;
			else len[u] = (A[v] != A[u]);
			make_tree(u, G, PP, D, A, prev, len);
		}
	}
}

void build_PP(VV &PP) {
	int N = PP[0].size();
	for (int k = 0, f = 1; f; k++) {
		f = 0;
		rep(i,N)
			if (PP[k][i] >= 0)
				PP[k + 1][i] = PP[k][PP[k][i]],f = 1;
	}
}

int lca(int u, int v, V &D, VV &PP) {
	if (D[u] > D[v])swap(u, v);
	for (int k = 0, d; (d = D[v] - D[u]); k++)
		if ((d >> k) & 1)v = PP[k][v];
	if (u == v)return v;
	for (int k = PP.size() - 1; k >= 0; k--)
		if (PP[k][u] != PP[k][v])
			u = PP[k][u], v = PP[k][v];
	return PP[0][u];
}
int underroot(int root, int v, V &D, VV &PP) {
	int sz = D[v] - D[root] - 1;
	for (int k = 0; sz; k++, sz >>= 1) {
		if (sz & 1)v = PP[k][v];
	}
	return v;
}


int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	int N, Q;
	while (cin >> N) {
		V A(N);
		range(it, A)cin >> it;
		Graph g(N);
		rep(i, N - 1) {
			int x, y;
			cin >> x >> y; x--; y--;
			g[x].push_back(y);
			g[y].push_back(x);
		}

		V depth(N, 0), len(N), prev(N);
		VV parent(30, V(N, -1));
		len[0] = 0;
		prev[0] = A[0];
		make_tree(0, g, parent, depth, A, prev, len);
		build_PP(parent);


		cin >> Q;
		while (Q--) {
			int u, v, pu, pv;
			cin >> u >> v; u--; v--;
			if (depth[u] > depth[v]) swap(u, v);
			int root = lca(u, v, depth, parent);
			int l = depth[v] - depth[u];
			if (root == u) {
				if (l > len[v] || l % 2 == 0 || l < 3) {
					cout << "NO" << endl;
					continue;
				}
				pu = underroot(u, v, depth, parent);
				pv = parent[0][v];
				if (!checkKadomatsu(A[pu], A[u], A[v])) { cout << "NO" << endl; continue; }
				if (!checkKadomatsu(A[pv], A[v], A[u])) { cout << "NO" << endl; continue; }
				cout << "YES" << endl;
			}
			else {
				int lu = depth[u] - depth[root];
				int lv = depth[v] - depth[root];
				if (lu > len[u] || lv > len[v] || (lu + lv) % 2 == 0 || (lu + lv) < 3) { cout << "NO" << endl; continue; }
				pu = parent[0][u];
				pv = parent[0][v];
				if(!checkKadomatsu(A[pu],A[u],A[v])) { cout << "NO" << endl; continue; }
				if (!checkKadomatsu(A[pv], A[v], A[u])) { cout << "NO" << endl; continue; }
				pv = underroot(root, v, depth, parent);
				pu = underroot(root, u, depth, parent);
				if (!checkKadomatsu(A[pu], A[root], A[pv])) { cout << "NO" << endl; continue; }
				cout << "YES" << endl;
			}
		}
	}
	return 0;
}
0