結果

問題 No.363 門松サイクル
コンテスト
ユーザー rickytheta
提出日時 2016-04-19 00:05:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 161 ms / 4,000 ms
コード長 2,978 bytes
コンパイル時間 1,751 ms
コンパイル使用メモリ 165,660 KB
実行使用メモリ 30,500 KB
最終ジャッジ日時 2024-10-04 13:59:32
合計ジャッジ時間 5,310 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:40:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
main.cpp:41:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   41 |   REP(i,n)scanf("%d",&a[i]);
      |           ~~~~~^~~~~~~~~~~~
main.cpp:44:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   44 |     scanf("%d%d",&x,&y);
      |     ~~~~~^~~~~~~~~~~~~~
main.cpp:79:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   79 |   scanf("%d",&q);
      |   ~~~~~^~~~~~~~~
main.cpp:83:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   83 |     scanf("%d%d",&s,&t);
      |     ~~~~~^~~~~~~~~~~~~~

ソースコード

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