結果

問題 No.363 門松サイクル
ユーザー ryofjtryofjt
提出日時 2016-09-12 20:31:34
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,519 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 52,068 KB
最終ジャッジ日時 2024-04-27 02:22:17
合計ジャッジ時間 2,725 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:8:9: error: ‘vector’ does not name a type
    8 | typedef vector<int> V;
      |         ^~~~~~
main.cpp:13:1: error: ‘V’ does not name a type
   13 | V t[100000];
      | ^
main.cpp: In function ‘void dfs(int)’:
main.cpp:24:20: error: ‘t’ was not declared in this scope
   24 |         for(int i: t[x]){
      |                    ^
main.cpp: In function ‘int main()’:
main.cpp:109:17: error: ‘t’ was not declared in this scope
  109 |                 t[x].push_back(y);
      |                 ^
main.cpp:100:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  100 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:102:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  102 |                 scanf("%d", &a[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:106:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  106 |                 scanf("%d%d", &x, &y);
      |                 ~~~~~^~~~~~~~~~~~~~~~
main.cpp:116:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
main.cpp:119:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  119 |                 scanf("%d%d", &u, &v);
      |                 ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <algorithm>

#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef vector<int> V;
typedef long long ll;

int n;
int a[100000];
V t[100000];
int d[100000];
int p[17][100000];
int q[17][100000];
bool km[17][100000];

bool is_km(int p, int q, int r){
	return ll(a[p] - a[q]) * (a[r] - a[q]) > 0 && a[p] != a[r];
}

void dfs(int x){
	for(int i: t[x]){
		if(d[i] == -1){
			d[i] = d[x] + 1;
			p[0][i] = x;
			dfs(i);
		}
	}
}
void init(){
	fill_n(d + 1, n - 1, -1);
	p[0][0] = -1;
	dfs(0);
	rep(i, n){
		q[0][i] = i;
	}
	fill_n(km[0] + 1, n - 1, true);
	for(int i = 1; i < 17; ++i){
		rep(j, n){
			int v = p[i - 1][j];
			if(v != -1){
				p[i][j] = p[i - 1][v];
				q[i][j] = q[i - 1][v];
				km[i][j] = km[i - 1][j] && km[i - 1][v] && is_km(p[0][v], v, q[i - 1][j]);
			}
			else{
				p[i][j] = q[i][j] = -1;
				km[i][j] = false;
			}
		}
	}
}

#include <iostream>

int up(int v, int x){
	rep(i, 17){
		if(x >> i & 1){
			v = p[i][v];
		}
	}
	return v;
}
int lca(int u, int v){
	if(d[u] > d[v]){
		swap(u, v);
	}
	v = up(v, d[v] - d[u]);
	if(u == v){
		return u;
	}
	for(int i = 17 - 1; i >= 0; --i){
		if(p[i][u] != p[i][v]){
			u = p[i][u];
			v = p[i][v];
		}
	}
	return p[0][u];
}

bool is_kml(int u, int v){
	int x = d[v] - d[u];
	rep(i, 17){
		if(x >> i & 1){
			int w = p[i][v];
			if(!km[i][v] || (w != u && !km[1][q[i][v]])){
				return false;
			}
			v = w;
		}
	}
	return true;
}



int main(){
	scanf("%d", &n);
	rep(i, n){
		scanf("%d", &a[i]);
	}
	rep(i, n - 1){
		int x, y;
		scanf("%d%d", &x, &y);
		--x;
		--y;
		t[x].push_back(y);
		t[y].push_back(x);
	}

	init();

	int q;
	scanf("%d", &q);
	rep(i, q){
		int u, v;
		scanf("%d%d", &u, &v);
		--u;
		--v;
		if(d[u] > d[v]){
			swap(u, v);
		}
		int c = lca(u, v);

		/*
		cout << "lca: " << c + 1 << endl;
		cout << "v: " << v + 1 << endl;
		cout << "u: " << u + 1 << endl;
		cout << "c1: " << up(v, d[v] - d[c] - 1) + 1 << endl;
		cout << "c2: " << up(u, d[u] - d[c] - 1) + 1 << endl;
		cout << "about c:" << is_km(up(u, d[u] - d[c] - 1), c, up(v, d[v] - d[c] - 1)) << endl;
		cout << "cv: " << is_kml(c, v) << endl;
		cout << "cu: " << is_kml(c, u) << endl;
		*/

		if(
			u == c && d[v] - d[c] >= 2 && is_kml(c, v) && is_km(v, c, up(v, d[v] - d[c] - 1)) && is_km(c, v, p[0][v]) ||
			u != c && is_kml(c, v) && is_kml(c, u) && is_km(up(u, d[u] - d[c] - 1), c, up(v, d[v] - d[c] - 1)) && is_km(u, v, p[0][v]) && is_km(v, u, p[0][u])
		){
			puts("YES");
		}
		else{
			puts("NO");
		}
	}
	return 0;
}
0