結果
| 問題 |
No.363 門松サイクル
|
| コンテスト | |
| ユーザー |
 kei
|
| 提出日時 | 2018-11-11 22:29:36 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,076 bytes |
| コンパイル時間 | 2,050 ms |
| コンパイル使用メモリ | 198,992 KB |
| 実行使用メモリ | 60,044 KB |
| 最終ジャッジ日時 | 2024-12-15 05:48:12 |
| 合計ジャッジ時間 | 14,416 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 3 WA * 24 |
ソースコード
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
/*
<url:https://yukicoder.me/problems/no/363>
問題文============================================================
=================================================================
解説=============================================================
ref : https://drive.google.com/file/d/0B8GpBQ5LDTd6QjZIY1VUckxWZ0U/view
================================================================
*/
map<ll,ll> A;
bool isKadomatsu(ll a,ll b,ll c){
if(a == 0 || b == 0 || c == 0) return false;
if(a == b || b == c || c == a) return false;
if(a > b && c > b) return true;
if(a < b && c < b) return true;
return false;
}
struct edge{
ll u,v,c;
edge():u(0),v(0),c(0){}
edge(ll u,ll v,ll c):u(u),v(v),c(c){}
};
typedef vector<vector<edge>> Graph;
Graph G;
class LCA{
public:
const ll n = 0;
const ll log2_n = 0;
vector<vector<ll>> parent;
vector<ll> depth;
LCA();
LCA(const Graph &g,ll root):n((ll)g.size()),log2_n(log2(n)+1),parent(log2_n,vector<ll>(n)),depth(n){
dfs(g,root,-1,0);
for(int k = 0; k+1 < log2_n; k++){
for(int v = 0; v < (int)g.size();v++){
if(parent[k][v] < 0) parent[k+1][v] = -1;
else parent[k+1][v] = parent[k][parent[k][v]];
}
}
}
void dfs(const Graph &g,ll v,ll p,ll d){
parent[0][v] = p; depth[v] = d;
for(auto &e :g[v]){
if(e.v != p) dfs(g, e.v, v, d+1);
}
}
ll get(ll u,ll v){
if(depth[u] > depth[v]) swap(u,v);
for(int k = 0; k < log2_n; k++){
if(((depth[v]-depth[u])>>k) & 1) v = parent[k][v];
}
if(u == v) return u;
for(int k = (int)log2_n - 1; k >= 0; k--){
if(parent[k][u] != parent[k][v]){
u = parent[k][u]; v = parent[k][v];
}
}
return parent[0][u];
}
ll get_parent(ll v,ll p){
ll d = depth[v] - depth[p] - 1;
if(d == -1) return -1;
for(int k = 0; k < log2_n; k++){
if((d>>k) & 1) v = parent[k][v];
}
return v;
}
};
vector<vector<int>> tG;
vector<int> checked;
void make_tree(int n,vector<vector<int>>& tG,vector<int>& checked){
checked[n] = true;
for(auto next:tG[n]){
if(checked[next]) continue;
G[n].push_back(edge(n,next,0));
make_tree(next,tG,checked);
}
}
void solve(){
int N; cin >> N;
for(int i = 0; i < N;i++){
ll _A; cin >> _A;
A[i] = _A;
}
//vector<ll> A(N); for(auto& in:A) cin >> in;
tG.resize(N);
checked.resize(N);
for(int i = 0; i < N-1;i++){
int x,y; cin >> x >> y; x--;y--;
tG[x].push_back(y); tG[y].push_back(x);
}
G.resize(N);
int root = 0;
make_tree(root,tG,checked);
LCA lca(G,root);
vector<vector<ll>> kadomatsu(lca.log2_n,vector<ll>(lca.n));
for(ll n = 0; n < N;n++){
if(lca.depth[n] < 2) continue;
ll pn = lca.parent[0][n], ppn = lca.parent[0][pn];
if(isKadomatsu(A[n],A[pn],A[ppn])){
kadomatsu[0][n] = 1;
}
}
for(int k = 0; k+1 < lca.log2_n; k++){
for(int v = 0; v < N;v++){
kadomatsu[k+1][v] = kadomatsu[k][v] & kadomatsu[k][lca.parent[k][v]];
}
}
// cout << kadomatsu << endl;
// cout << A << endl;
int Q; cin >> Q;
while(Q--){
ll u,v; cin >> u >> v; u--; v--;
ll p = lca.get(u,v);
ll pu = lca.get_parent(u, p);
ll pv = lca.get_parent(v, p);
ll qu = lca.parent[0][u];
ll qv = lca.parent[0][v];
bool ok = true;
// cout << "====" << endl;
// cout << u << " " << v << " " << qu << " " << qv << " " << pu << " " << pv << endl;
if(qu != -1) ok &= isKadomatsu(A[qu], A[u], A[v]);
// cout << ok << endl;
if(pv != -1) ok &= isKadomatsu(A[u], A[v], A[qv]);
// cout << ok << endl;
if(pu != -1 && pv != -1) ok &= isKadomatsu(A[pu], A[p], A[pv]);
// cout << ok << endl;
ll dv = max(lca.depth[v] - lca.depth[p] -2,0LL);
for(int k = 0; k < lca.log2_n; k++){
if((dv>>k) & 1){
ok &= kadomatsu[k][v];
v = lca.parent[k][v];
if(v == -1) break;
}
}
ll du = max(lca.depth[u] - lca.depth[p] - 2,0LL);
for(int k = 0; k < lca.log2_n; k++){
if((du>>k) & 1){
ok &= kadomatsu[k][u];
u = lca.parent[k][u];
if(u == -1) break;
}
}
if(ok){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
// cout << tG << endl;
// for(int i = 0; i < N;i++){
// cout << i << " : "; for(auto v:G[i]) cout << v.v << " "; cout << endl;
// }
}
int main(void) {
cin.tie(0); ios_base::sync_with_stdio(false);
solve();
return 0;
}