結果

問題 No.363 門松サイクル
ユーザー yaoshimaxyaoshimax
提出日時 2016-04-18 20:24:55
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 338 ms / 4,000 ms
コード長 4,231 bytes
コンパイル時間 663 ms
コンパイル使用メモリ 71,684 KB
実行使用メモリ 19,060 KB
最終ジャッジ日時 2024-04-15 03:39:37
合計ジャッジ時間 5,144 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
15,320 KB
testcase_01 AC 6 ms
15,380 KB
testcase_02 AC 7 ms
15,372 KB
testcase_03 AC 7 ms
15,364 KB
testcase_04 AC 7 ms
15,320 KB
testcase_05 AC 6 ms
15,344 KB
testcase_06 AC 7 ms
15,348 KB
testcase_07 AC 6 ms
15,368 KB
testcase_08 AC 6 ms
15,244 KB
testcase_09 AC 84 ms
16,728 KB
testcase_10 AC 75 ms
16,872 KB
testcase_11 AC 179 ms
18,308 KB
testcase_12 AC 183 ms
18,048 KB
testcase_13 AC 164 ms
18,032 KB
testcase_14 AC 134 ms
18,104 KB
testcase_15 AC 164 ms
18,160 KB
testcase_16 AC 120 ms
17,076 KB
testcase_17 AC 163 ms
18,384 KB
testcase_18 AC 210 ms
18,420 KB
testcase_19 AC 112 ms
19,060 KB
testcase_20 AC 190 ms
18,504 KB
testcase_21 AC 205 ms
18,416 KB
testcase_22 AC 173 ms
18,356 KB
testcase_23 AC 159 ms
17,716 KB
testcase_24 AC 5 ms
15,236 KB
testcase_25 AC 6 ms
15,212 KB
testcase_26 AC 209 ms
18,384 KB
testcase_27 AC 149 ms
18,576 KB
testcase_28 AC 338 ms
18,356 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:63:9: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |    scanf("%d",&N);
      |    ~~~~~^~~~~~~~~
main.cpp:70:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |       scanf("%d%d",&x,&y);
      |       ~~~~~^~~~~~~~~~~~~~
main.cpp:119:9: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  119 |    scanf("%d",&Q);
      |    ~~~~~^~~~~~~~~
main.cpp:122:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  122 |       scanf("%d%d",&u,&v);
      |       ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <climits>
#include <vector>
#include <cstdio>
#include <cstring>
#include <set>
#include <stack>
using namespace std;
bool kadomatsu(int x,int y, int z){
   if( x==y || y==z || z==x ) return false;
   if( x<y && y>z ) return true;
   if( x>y && y<z) return true;
   return false;
}

int depth[100000];
int parent[18][100000];
int val[100000];
bool iskadsequence[17][100000];
vector<int> edge[100000];
int up(int cur, int d){
   if( d==0 ) return cur;
   int ex=0;
   int ret = cur;
   while( (1<<ex)*2 <= d ) ex++;
   while( d!= 0&&ex>=0 ){
      if( (d&(1<<ex))!=0){
         ret = parent[ex][ret];
         d-=(1<<ex);
      }
      ex--;
   }
   return ret;
}
int lca(int u, int v){
   if( u==v ) return u;
   int left=0;
   int right=depth[u];
   while( left+1 < right ){
      int mid=(left+right)/2;
      if( up(u,mid)==up(v,mid) ){
         right = mid;
      }
      else{
         left=mid;
      }
   }
   return up(u,right);
}
bool checkKadSeq(int u, int d){
   if( d<= 1 ) return true;
   int ex=0;
   while( (1<<ex)*2 <= d ) ex++;
   if( iskadsequence[ex][u]== false ) return false;
   if( d==(1<<ex) ) return true;
   int p = parent[ex][u];
   if( !kadomatsu(val[parent[0][p]],val[p],val[up(u, depth[u]-depth[p]-1)]) ) return false;
   return checkKadSeq(parent[ex][u], d-(1<<ex));
}

int main(){
   int N;
   scanf("%d",&N);
   memset(depth,-1,sizeof(depth));
   memset(parent,-1,sizeof(parent));
   memset( iskadsequence,false,sizeof(iskadsequence));
   for( int i = 0 ; i < N; i++ ) cin >> val[i];
   for( int i = 0 ; i <N-1; i++ ){
      int x,y;
      scanf("%d%d",&x,&y);
      x--;y--;
      edge[x].push_back(y);
      edge[y].push_back(x);
   }
   stack<int> st;
   st.push(0);
   depth[0]=0;
   parent[0][0]=-1;
   while( !st.empty() ){
      int cur = st.top();
      st.pop();
      for( int ei=0; ei < (int)edge[cur].size(); ei++){
         int nxt = edge[cur][ei];
         if( depth[nxt]!=-1  ) continue;
         depth[nxt]=depth[cur]+1;
         parent[0][nxt]=cur;
         iskadsequence[0][nxt]=true;
         int tmpCur=cur;
         int tmpNxt=nxt;
         for( int i = 0;parent[i][tmpCur]!=-1;i++){
            parent[i+1][nxt]=parent[i][tmpCur];
            iskadsequence[i+1][nxt]=(iskadsequence[i][nxt]&iskadsequence[i][tmpCur]&kadomatsu(val[parent[0][tmpCur]],val[tmpCur],val[tmpNxt]));
            tmpCur=parent[i][tmpCur];
            tmpNxt=parent[i][tmpNxt];
         }
         st.push(nxt);
      }
   }
   /*
   for( int i = 0 ; i < N; i++ ){
     cout << depth[i]<<", ";
   }
   cout << endl;
   for( int i = 0 ; i <N; i++ ){
      cout <<i<<": ";
      for( int j = 0 ; j < 17; j++ ){
         if( parent[j][i]!=-1 ) cout << (1<<j) <<"="<<parent[j][i];
      }
      cout << endl;
   }
   for( int i = 0 ; i <N; i++ ){
      cout <<i<<": ";
      for( int j = 0 ; j < 17; j++ ){
         if( parent[j][i]!=-1 ) cout << (1<<j) <<"="<<iskadsequence[j][i];
      }
      cout << endl;
   }*/
   int Q;
   scanf("%d",&Q);
   for( int i = 0 ; i < Q; i++ ){
      int u,v;
      scanf("%d%d",&u,&v);
      u--;
      v--;
      if( depth[u] > depth[v] ){
         swap(u,v);
      }
      if( parent[0][u]==v || parent[0][v]== u){
         printf("NO\n");
         continue;
      }
      int v2=up(v,depth[v]-depth[u]);
      if( v2 == u ){
         int child_v=up(v,depth[v]-depth[u]-1);
         if( checkKadSeq(v,depth[v]-depth[u])
             && kadomatsu(val[parent[0][v]],val[v],val[u])
             && kadomatsu(val[child_v],val[u],val[v])){
                    printf("YES\n");
         }
         else{
            printf("NO\n");
         }
         continue;
      }
      int p=lca(u,v2);
      int child_u=up(u,depth[u]-depth[p]-1);
      int child_v=up(v,depth[v]-depth[p]-1);
 //     cout << v2<<", "<<p <<", "<< child_u << ", "<< child_v<<endl;
      if( kadomatsu(val[child_u],val[p],val[child_v])
            && checkKadSeq(u,depth[u]-depth[p])
            && checkKadSeq(v,depth[v]-depth[p])
            && kadomatsu(val[u],val[v],val[parent[0][v]])
            && kadomatsu(val[v],val[u],val[parent[0][u]])
            ){
            printf("YES\n");
      }
      else{
            printf("NO\n");
      }
   }
   return 0;        
}
0