結果

問題 No.363 門松サイクル
ユーザー btk
提出日時 2016-05-24 14:50:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 365 ms / 4,000 ms
コード長 3,109 bytes
コンパイル時間 1,792 ms
コンパイル使用メモリ 177,184 KB
実行使用メモリ 33,104 KB
最終ジャッジ日時 2024-10-11 05:08:35
合計ジャッジ時間 9,641 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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

/*
* Problem link
* http://yukicoder.me/problems/1024
*/
/*門松を許すな！！！！！！！！！！！！！！！！！！！！！*/
#include<bits/stdc++.h>
using namespace std;
struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init;
#define rep(i,n) for(auto i=(n)*0;i<n;i++)
#define range(it,v) for(auto &it:v)
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<int> E;
typedef vector<E> Graph;
bool checkKadomatsu(int a, int b, int c) {
    return (a != c) ? ((a > b&&b < c) || (a<b&&b>c)) : false;
}
void make_tree(int v, Graph &G, VV &PP, V &D, V &A, V &prev, V& len) {
    range(u, G[v]) {
        if (u != PP[0][v]) {
            D[u] = D[v] + 1;
            PP[0][u] = v;
            prev[u] = A[v];
            if (checkKadomatsu(prev[v],A[v],A[u]))
                len[u] = len[v] + 1;
            else len[u] = (A[v] != A[u]);
            make_tree(u, G, PP, D, A, prev, len);
        }
    }
}
void build_PP(VV &PP) {
    int N = PP[0].size();
    for (int k = 0, f = 1; f; k++) {
        f = 0;
        rep(i,N)
            if (PP[k][i] >= 0)
                PP[k + 1][i] = PP[k][PP[k][i]],f = 1;
    }
}
int lca(int u, int v, V &D, VV &PP) {
    if (D[u] > D[v])swap(u, v);
    for (int k = 0, d; (d = D[v] - D[u]); k++)
        if ((d >> k) & 1)v = PP[k][v];
    if (u == v)return v;
    for (int k = PP.size() - 1; k >= 0; k--)
        if (PP[k][u] != PP[k][v])
            u = PP[k][u], v = PP[k][v];
    return PP[0][u];
}
int underroot(int root, int v, V &D, VV &PP) {
    int sz = D[v] - D[root] - 1;
    for (int k = 0; sz; k++, sz >>= 1) {
        if (sz & 1)v = PP[k][v];
    }
    return v;
}
int main() {
#ifdef INPUT_FROM_FILE
    ifstream cin("sample.in");
    ofstream cout("sample.out");
#endif
    int N, Q;
    while (cin >> N) {
        V A(N);
        range(it, A)cin >> it;
        Graph g(N);
        rep(i, N - 1) {
            int x, y;
            cin >> x >> y; x--; y--;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        V depth(N, 0), len(N), prev(N);
        VV parent(30, V(N, -1));
        len[0] = 0;
        prev[0] = A[0];
        make_tree(0, g, parent, depth, A, prev, len);
        build_PP(parent);
        cin >> Q;
        while (Q--) {
            int u, v, pu, pv;
            cin >> u >> v; u--; v--;
            if (depth[u] > depth[v]) swap(u, v);
            int root = lca(u, v, depth, parent);
            int l = depth[v] - depth[u];
            if (root == u) {
                if (l > len[v] || l % 2 == 0 || l < 3) {
                    cout << "NO" << endl;
                    continue;
                }
                pu = underroot(u, v, depth, parent);
                pv = parent[0][v];
                if (!checkKadomatsu(A[pu], A[u], A[v])) { cout << "NO" << endl; continue; }
                if (!checkKadomatsu(A[pv], A[v], A[u])) { cout << "NO" << endl; continue; }
                cout << "YES" << endl;
            }
            else {
                int lu = depth[u] - depth[root];
                int lv = depth[v] - depth[root];
                if (lu > len[u] || lv > len[v] || (lu + lv) % 2 == 0 || (lu + lv) < 3) { cout << "NO" << endl; continue; }
                pu = parent[0][u];
                pv = parent[0][v];
                if(!checkKadomatsu(A[pu],A[u],A[v])) { cout << "NO" << endl; continue; }
                if (!checkKadomatsu(A[pv], A[v], A[u])) { cout << "NO" << endl; continue; }
                pv = underroot(root, v, depth, parent);
                pu = underroot(root, u, depth, parent);
                if (!checkKadomatsu(A[pu], A[root], A[pv])) { cout << "NO" << endl; continue; }
                cout << "YES" << endl;
            }
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0