結果

問題 No.363 門松サイクル
ユーザー rickythetarickytheta
提出日時 2016-04-19 00:05:54
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 219 ms / 4,000 ms
コード長 2,978 bytes
コンパイル時間 2,257 ms
コンパイル使用メモリ 151,668 KB
実行使用メモリ 30,480 KB
最終ジャッジ日時 2023-07-27 16:24:15
合計ジャッジ時間 6,761 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
10,148 KB
testcase_01 AC 3 ms
10,032 KB
testcase_02 AC 5 ms
10,188 KB
testcase_03 AC 4 ms
10,240 KB
testcase_04 AC 4 ms
10,148 KB
testcase_05 AC 5 ms
10,072 KB
testcase_06 AC 5 ms
10,060 KB
testcase_07 AC 5 ms
10,324 KB
testcase_08 AC 5 ms
10,136 KB
testcase_09 AC 72 ms
19,880 KB
testcase_10 AC 65 ms
19,956 KB
testcase_11 AC 154 ms
29,936 KB
testcase_12 AC 180 ms
29,660 KB
testcase_13 AC 141 ms
29,724 KB
testcase_14 AC 109 ms
27,472 KB
testcase_15 AC 130 ms
29,728 KB
testcase_16 AC 126 ms
24,368 KB
testcase_17 AC 209 ms
29,916 KB
testcase_18 AC 165 ms
29,940 KB
testcase_19 AC 119 ms
30,480 KB
testcase_20 AC 166 ms
29,952 KB
testcase_21 AC 219 ms
29,912 KB
testcase_22 AC 156 ms
30,016 KB
testcase_23 AC 206 ms
27,344 KB
testcase_24 AC 4 ms
10,040 KB
testcase_25 AC 4 ms
10,048 KB
testcase_26 AC 127 ms
29,912 KB
testcase_27 AC 128 ms
29,856 KB
testcase_28 AC 173 ms
29,856 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

// ARC048 D をコピペ

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

const int INF = 830252521;

int n;
int a[125252];
vi g[125252];

int depth[125252];
int anc[125252][20];
int query[125252][20];

bool kado(int s,int t,int u){
  int x=a[s],y=a[t],z=a[u];
  return (x<y&&y>z&&x!=z) || (x>y&&y<z&&x!=z);
}

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;
    g[x].push_back(y);
    g[y].push_back(x);
  }

  REP(i,n) depth[i]=INF;
  REP(i,n)REP(k,20) anc[i][k]=query[i][k]=INF;
  queue<int> Q;
  depth[0] = 0;
  Q.push(0);
  while(!Q.empty()){
    int pos = Q.front(); Q.pop();
    int d = depth[pos];
    REP(i,g[pos].size()){
      int to = g[pos][i];
      if(depth[to]!=INF)continue;
      depth[to] = d+1;
      Q.push(to);
      // ダブリング準備
      anc[to][0] = pos;
      query[to][0] = (d+1<2?0:kado(to,pos,anc[pos][0]));
      int id = 1;
      int cur = pos;
      while(anc[cur][id-1]!=INF){
        int next = anc[cur][id-1];
        anc[to][id] = next;
        query[to][id] = query[to][id-1] & query[cur][id-1];
        cur = next;
        ++id;
      }
    }
  }

  int q;
  scanf("%d",&q);

  while(q--){
    int s,t;
    scanf("%d%d",&s,&t);
    --s; --t;
    if(depth[s]>depth[t])swap(s,t);
    int x=s, y=t;
    int diff = depth[y]-depth[x];
    REP(k,20){
      if(diff&1) y = anc[y][k];
      diff>>=1;
    }
    REP(_k,20){
      int k = 20-1-_k;
      if(anc[x][k]!=INF && anc[x][k]!=anc[y][k]){
        x = anc[x][k];
        y = anc[y][k];
      }
    }
    bool flag = true;
    if(x!=y){
      // s --- x - lca - y --- t
      int lca = anc[x][0];
      flag &= kado(x,lca,y);
      flag &= kado(anc[s][0],s,t);
      flag &= kado(anc[t][0],t,s);
      diff = max(0,depth[s]-depth[lca]-1);
      x = s;
      REP(k,20){
        if(diff&1){
          flag &= query[x][k];
          x = anc[x][k];
        }
        diff >>= 1;
      }
      diff = max(0,depth[t]-depth[lca]-1);
      x = t;
      REP(k,20){
        if(diff&1){
          flag &= query[x][k];
          x = anc[x][k];
        }
        diff >>= 1;
      }
    }else{
      // s=x=lca=y --- t
      diff = max(0,depth[t]-depth[s]-1);
      x = t;
      REP(k,20){
        if(diff&1){
          flag &= query[x][k];
          x = anc[x][k];
        }
        diff >>= 1;
      }
      flag &= kado(x,s,t);
      flag &= kado(s,t,anc[t][0]);
    }
    if(flag)puts("YES");
    else puts("NO");
  }
  return 0;
}
0