結果

問題 No.363 門松サイクル
ユーザー kosakkunkosakkun
提出日時 2016-12-27 18:57:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,135 bytes
コンパイル時間 945 ms
コンパイル使用メモリ 96,412 KB
実行使用メモリ 18,304 KB
最終ジャッジ日時 2024-05-08 20:53:13
合計ジャッジ時間 6,834 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,016 KB
testcase_01 AC 3 ms
5,888 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 2 ms
5,888 KB
testcase_25 WA -
testcase_26 AC 254 ms
18,304 KB
testcase_27 WA -
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
#define PB_VEC(Itr1,Itr2) (Itr1).insert((Itr1).end(),(Itr2).begin(),(Itr2).end())
#define UNIQUE(Itr) sort((Itr).begin(),(Itr).end()); (Itr).erase(unique((Itr).begin(),(Itr).end()),(Itr).end())
#define LBOUND(Itr,val) lower_bound((Itr).begin(),(Itr).end(),(val))
#define UBOUND(Itr,val) upper_bound((Itr).begin(),(Itr).end(),(val))
typedef long long ll;

vector<int> G[100010];
int A1[100010],A2[100010];
bool high_low1[100010];
bool high_low2[100010];
bool used[100010];
int dep[100010];

void dfs1(int v, bool hl,int depth){
    if(used[v])return;
    used[v]=true;
    dep[v]=depth;
    high_low1[v]=hl;
    REP(i,G[v].size()){
        if(A1[v]==-1){
            A1[G[v][i]]=-1;
            dfs1(G[v][i],!hl,depth+1);
        }else if(hl){
            if(A1[v]>A1[G[v][i]]){
                dfs1(G[v][i],!hl,depth+1);
            }else{
                A1[G[v][i]]=-1;
                dfs1(G[v][i],!hl,depth+1);
            }
        }else{
            if(A1[v]<A1[G[v][i]]){
                dfs1(G[v][i],!hl,depth+1);
            }else{
                A1[G[v][i]]=-1;
                dfs1(G[v][i],!hl,depth+1);
            }
        }
    }
}

void dfs2(int v, bool hl){
    if(used[v])return;
    used[v]=true;
    high_low2[v]=hl;
    REP(i,G[v].size()){
        if(!used[G[v][i]]){
        if(A2[v]==-1){
            A2[G[v][i]]=-1;
            dfs2(G[v][i],!hl);
        }else if(hl){
            if(A2[v]>A2[G[v][i]]){
                dfs2(G[v][i],!hl);
            }else{
                A2[G[v][i]]=-1;
                dfs2(G[v][i],!hl);
            }
        }else{
            if(A2[v]<A2[G[v][i]]){
                dfs2(G[v][i],!hl);
            }else{
                A2[G[v][i]]=-1;
                dfs2(G[v][i],!hl);
            }
        }
        }
    }
}

int main(){
    
    int n; cin>>n;
    REP(i,n)cin>>A1[i+1];
    REP(i,n)A2[i+1]=A1[i+1];
    REP(i,n-1){
        int a,b; cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    REP(i,100010)used[i]=false;
    dfs1(1,true,0);
    REP(i,100010)used[i]=false;
    dfs2(1,false);
    
   /* for(int i=1;i<=7;i++){
        cout<<i<<":"<<A1[i]<<" "<<A2[i]<<" "<<high_low1[i]<<" "<<high_low2[i]<<endl;
    }*/
    
    int q; cin>>q;
    REP(i,q){
        bool flag1=true,flag2=true;
        int u,v; cin>>u>>v;
        if(A1[u]<0||A1[v]<0)flag1=false;
        else if(high_low1[u]==high_low1[v])flag1=false;
        if(A2[u]<0||A2[v]<0)flag2=false;
        else if(high_low2[u]==high_low2[v])flag2=false;
        
        int length=dep[v]+dep[u];
        if(length<3)cout<<"NO"<<endl;
        else if(flag1||flag2)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    
    
    return 0;
}
0