結果

問題 No.363 門松サイクル
ユーザー yaoshimaxyaoshimax
提出日時 2016-04-18 20:24:55
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 296 ms / 4,000 ms
コード長 4,231 bytes
コンパイル時間 646 ms
コンパイル使用メモリ 70,768 KB
実行使用メモリ 18,992 KB
最終ジャッジ日時 2024-10-04 13:55:14
合計ジャッジ時間 5,119 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
15,344 KB
testcase_01 AC 5 ms
15,328 KB
testcase_02 AC 6 ms
15,140 KB
testcase_03 AC 5 ms
15,384 KB
testcase_04 AC 6 ms
15,308 KB
testcase_05 AC 5 ms
15,344 KB
testcase_06 AC 5 ms
15,296 KB
testcase_07 AC 5 ms
15,172 KB
testcase_08 AC 6 ms
15,232 KB
testcase_09 AC 77 ms
16,748 KB
testcase_10 AC 70 ms
17,072 KB
testcase_11 AC 167 ms
18,408 KB
testcase_12 AC 167 ms
17,956 KB
testcase_13 AC 153 ms
18,164 KB
testcase_14 AC 123 ms
18,040 KB
testcase_15 AC 153 ms
18,032 KB
testcase_16 AC 117 ms
17,144 KB
testcase_17 AC 138 ms
18,224 KB
testcase_18 AC 179 ms
18,404 KB
testcase_19 AC 109 ms
18,992 KB
testcase_20 AC 172 ms
18,544 KB
testcase_21 AC 174 ms
18,556 KB
testcase_22 AC 168 ms
18,532 KB
testcase_23 AC 141 ms
17,736 KB
testcase_24 AC 5 ms
15,344 KB
testcase_25 AC 5 ms
15,240 KB
testcase_26 AC 200 ms
18,364 KB
testcase_27 AC 132 ms
18,420 KB
testcase_28 AC 296 ms
18,376 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