結果

問題 No.363 門松サイクル
コンテスト
ユーザー FF256grhy
提出日時 2016-04-19 15:24:25
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 171 ms / 4,000 ms
コード長 3,074 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 26,344 KB
実行使用メモリ 20,280 KB
最終ジャッジ日時 2024-10-04 14:06:45
合計ジャッジ時間 3,943 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:63:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:64:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |         for(i = 0; i < n; i++) { scanf("%d", &a[i]); }
      |                                  ~~~~~^~~~~~~~~~~~~
main.cpp:65:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   65 |         for(i = 0; i < n - 1; i++) { scanf("%d%d", &x[i], &y[i]); x[i]--; y[i]--; }
      |                                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:66:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   66 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
main.cpp:67:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |         for(i = 0; i < q    ; i++) { scanf("%d%d", &u[i], &v[i]); u[i]--; v[i]--; }
      |                                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>

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

#define MAX 100000
#define NIL  0
#define ROOT 0

int n, a[MAX], x[MAX], y[MAX], q, u[MAX], v[MAX];
int first[MAX], last[MAX], list_val[MAX * 2 + 1], list_next[MAX * 2 + 1], ptr = 1;
int queue_val[MAX], get, set;
int height[MAX], ancestor[MAX][17], is_kado[MAX][17], flag[MAX];
// ancestor は 2^n 上のノード, is_kado は 2^n + 1 までが門松列かどうか

void add(int xx, int yy) {
	if(first[xx] == NIL) {
		first[xx] = ptr;
	} else {
		list_next[ last[xx] ] = ptr;
	}
	last[xx] = ptr;
	list_val[ptr] = yy;
	list_next[ptr] = NIL;
	ptr++;
}

int up(int s, int n) {
	int i = 0;
	while(n) {
		if(n % 2) { s = ancestor[s][i]; }
		n /= 2;
		i++;
	}
	return s;
}

int len(int n) {
	int i = 0;
	while(n) {
		n /= 2;
		i++;
	}
	return i;
}

int is_kado_func(int s, int t) {
	// s から tの次 まで
	int n = height[s] - height[t];
	int i, ans = 1;
	for(i = 0; i < len(n); i++) {
		if(n & (1 << i)) {
			ans &= is_kado[s][i];
			s = ancestor[s][i];
		}
	}
	return ans;
}

int main() {
	int i, j;
	scanf("%d", &n);
	for(i = 0; i < n; i++) { scanf("%d", &a[i]); }
	for(i = 0; i < n - 1; i++) { scanf("%d%d", &x[i], &y[i]); x[i]--; y[i]--; }
	scanf("%d", &q);
	for(i = 0; i < q    ; i++) { scanf("%d%d", &u[i], &v[i]); u[i]--; v[i]--; }
	
	for(i = 0; i < n - 1; i++) {
		add(x[i], y[i]);
		add(y[i], x[i]);
	}
	
	queue_val[set] = ROOT; set++;
	flag[ROOT] = 1;
	height[ROOT] = 0;
	while(get != set) {
		int qv = queue_val[get];
		int p = first[qv];
		while(p != NIL) {
			int lv = list_val[p];
			if(! flag[lv]) {
				flag[lv] = 1;
				queue_val[set] = lv; set++;
				height[lv] = height[qv] + 1;
				ancestor[lv][0] = qv;
				for(i = 0; i < len(height[lv]) - 1; i++) {
					ancestor[lv][i + 1] = ancestor[ ancestor[lv][i] ][i];
				}		
				if(height[lv] >= 2) {
					is_kado[lv][0] = isK( a[lv], a[ ancestor[lv][0] ], a[ ancestor[lv][1] ] );
					for(i = 0; i < len(height[lv] - 1) - 1; i++) {
						is_kado[lv][i + 1] = is_kado[lv][i] && is_kado[ ancestor[lv][i] ][i];
					}
				}
			}
			p = list_next[p];
		}
		get++;
	}
	
	
	for(i = 0; i < q; i++) {
		if(height[ u[i] ] < height[ v[i] ]) {
			int temp = u[i];
			u[i] = v[i];
			v[i] = temp;
		}
		
		int diff = height[ u[i] ] - height[ v[i] ];
		int s = up(u[i], diff);
		int t = v[i];
		int ans;
		if(s != t) {
			for(j = len(height[s]) - 1; 0 <= j; j--) {
				if(ancestor[s][j] != ancestor[t][j]) {
					s = ancestor[s][j];
					t = ancestor[t][j];
				}
			}
			int c = ancestor[s][0];
			int uu = ancestor[ u[i] ][0];
			int vv = ancestor[ v[i] ][0];
			
			ans = (
				isK(a[s], a[c], a[t]) &&
				isK(a[uu], a[u[i]], a[v[i]]) &&
				isK(a[vv], a[v[i]], a[u[i]]) &&
				is_kado_func(u[i], s) &&
				is_kado_func(v[i], t)
			);
		} else {
			int uu = ancestor[ u[i] ][0];
			int vv = up(u[i], diff - 1);
			
			ans = (
				isK(a[uu], a[u[i]], a[v[i]]) &&
				isK(a[vv], a[v[i]], a[u[i]]) &&
				is_kado_func(u[i], vv)
			);
		}
		
		printf("%s\n", ans ? "YES" : "NO");
	}
	
	return 0;
}
0