結果

問題 No.363 門松サイクル
ユーザー FF256grhy
提出日時 2016-04-19 15:24:25
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 171 ms / 4,000 ms
コード長 3,074 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 26,344 KB
実行使用メモリ 20,280 KB
最終ジャッジ日時 2024-10-04 14:06:45
合計ジャッジ時間 3,943 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:63:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:64:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |         for(i = 0; i < n; i++) { scanf("%d", &a[i]); }
      |                                  ~~~~~^~~~~~~~~~~~~
main.cpp:65:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   65 |         for(i = 0; i < n - 1; i++) { scanf("%d%d", &x[i], &y[i]); x[i]--; y[i]--; }
      |                                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:66:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   66 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
main.cpp:67:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |         for(i = 0; i < q    ; i++) { scanf("%d%d", &u[i], &v[i]); u[i]--; v[i]--; }
      |                                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
int isK(int a, int b, int c) {
    return ( (a < b && b > c && a != c) || (a > b && b < c && a != c) );
}
#define MAX 100000
#define NIL  0
#define ROOT 0
int n, a[MAX], x[MAX], y[MAX], q, u[MAX], v[MAX];
int first[MAX], last[MAX], list_val[MAX * 2 + 1], list_next[MAX * 2 + 1], ptr = 1;
int queue_val[MAX], get, set;
int height[MAX], ancestor[MAX][17], is_kado[MAX][17], flag[MAX];
// ancestor は 2^n 上のノード, is_kado は 2^n + 1 までが門松列かどうか
void add(int xx, int yy) {
    if(first[xx] == NIL) {
        first[xx] = ptr;
    } else {
        list_next[ last[xx] ] = ptr;
    }
    last[xx] = ptr;
    list_val[ptr] = yy;
    list_next[ptr] = NIL;
    ptr++;
}
int up(int s, int n) {
    int i = 0;
    while(n) {
        if(n % 2) { s = ancestor[s][i]; }
        n /= 2;
        i++;
    }
    return s;
}
int len(int n) {
    int i = 0;
    while(n) {
        n /= 2;
        i++;
    }
    return i;
}
int is_kado_func(int s, int t) {
    // s から tの次 まで
    int n = height[s] - height[t];
    int i, ans = 1;
    for(i = 0; i < len(n); i++) {
        if(n & (1 << i)) {
            ans &= is_kado[s][i];
            s = ancestor[s][i];
        }
    }
    return ans;
}
int main() {
    int i, j;
    scanf("%d", &n);
    for(i = 0; i < n; i++) { scanf("%d", &a[i]); }
    for(i = 0; i < n - 1; i++) { scanf("%d%d", &x[i], &y[i]); x[i]--; y[i]--; }
    scanf("%d", &q);
    for(i = 0; i < q    ; i++) { scanf("%d%d", &u[i], &v[i]); u[i]--; v[i]--; }
    
    for(i = 0; i < n - 1; i++) {
        add(x[i], y[i]);
        add(y[i], x[i]);
    }
    
    queue_val[set] = ROOT; set++;
    flag[ROOT] = 1;
    height[ROOT] = 0;
    while(get != set) {
        int qv = queue_val[get];
        int p = first[qv];
        while(p != NIL) {
            int lv = list_val[p];
            if(! flag[lv]) {
                flag[lv] = 1;
                queue_val[set] = lv; set++;
                height[lv] = height[qv] + 1;
                ancestor[lv][0] = qv;
                for(i = 0; i < len(height[lv]) - 1; i++) {
                    ancestor[lv][i + 1] = ancestor[ ancestor[lv][i] ][i];
                }       
                if(height[lv] >= 2) {
                    is_kado[lv][0] = isK( a[lv], a[ ancestor[lv][0] ], a[ ancestor[lv][1] ] );
                    for(i = 0; i < len(height[lv] - 1) - 1; i++) {
                        is_kado[lv][i + 1] = is_kado[lv][i] && is_kado[ ancestor[lv][i] ][i];
                    }
                }
            }
            p = list_next[p];
        }
        get++;
    }
    
    
    for(i = 0; i < q; i++) {
        if(height[ u[i] ] < height[ v[i] ]) {
            int temp = u[i];
            u[i] = v[i];
            v[i] = temp;
        }
        
        int diff = height[ u[i] ] - height[ v[i] ];
        int s = up(u[i], diff);
        int t = v[i];
        int ans;
        if(s != t) {
            for(j = len(height[s]) - 1; 0 <= j; j--) {
                if(ancestor[s][j] != ancestor[t][j]) {
                    s = ancestor[s][j];
                    t = ancestor[t][j];
                }
            }
            int c = ancestor[s][0];
            int uu = ancestor[ u[i] ][0];
            int vv = ancestor[ v[i] ][0];
            
            ans = (
                isK(a[s], a[c], a[t]) &&
                isK(a[uu], a[u[i]], a[v[i]]) &&
                isK(a[vv], a[v[i]], a[u[i]]) &&
                is_kado_func(u[i], s) &&
                is_kado_func(v[i], t)
            );
        } else {
            int uu = ancestor[ u[i] ][0];
            int vv = up(u[i], diff - 1);
            
            ans = (
                isK(a[uu], a[u[i]], a[v[i]]) &&
                isK(a[vv], a[v[i]], a[u[i]]) &&
                is_kado_func(u[i], vv)
            );
        }
        
        printf("%s\n", ans ? "YES" : "NO");
    }
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0