結果

問題 No.363 門松サイクル
ユーザー はまやんはまやんはまやんはまやん
提出日時 2017-04-22 05:07:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 184 ms / 4,000 ms
コード長 5,016 bytes
コンパイル時間 2,101 ms
コンパイル使用メモリ 182,156 KB
実行使用メモリ 25,216 KB
最終ジャッジ日時 2024-07-21 07:00:17
合計ジャッジ時間 7,548 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,016 KB
testcase_01 AC 4 ms
6,144 KB
testcase_02 AC 5 ms
6,272 KB
testcase_03 AC 4 ms
6,272 KB
testcase_04 AC 5 ms
6,272 KB
testcase_05 AC 4 ms
6,016 KB
testcase_06 AC 4 ms
6,144 KB
testcase_07 AC 5 ms
6,144 KB
testcase_08 AC 5 ms
6,144 KB
testcase_09 AC 59 ms
11,904 KB
testcase_10 AC 64 ms
12,160 KB
testcase_11 AC 138 ms
20,608 KB
testcase_12 AC 144 ms
19,072 KB
testcase_13 AC 145 ms
16,768 KB
testcase_14 AC 110 ms
15,872 KB
testcase_15 AC 126 ms
19,456 KB
testcase_16 AC 88 ms
16,128 KB
testcase_17 AC 180 ms
25,216 KB
testcase_18 AC 184 ms
17,536 KB
testcase_19 AC 120 ms
18,816 KB
testcase_20 AC 173 ms
17,664 KB
testcase_21 AC 168 ms
23,296 KB
testcase_22 AC 155 ms
17,280 KB
testcase_23 AC 122 ms
20,864 KB
testcase_24 AC 4 ms
6,144 KB
testcase_25 AC 3 ms
6,016 KB
testcase_26 AC 94 ms
25,216 KB
testcase_27 AC 95 ms
25,216 KB
testcase_28 AC 109 ms
21,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)



struct HLDecomposition {
    vector<vector<int>> g;

    // vid : id -> vid
    // head, heavy, parent : unknown
    // depth : id -> depth
    // inv : vid -> id
    vector<int> vid, head, heavy, parent, depth, inv;

    HLDecomposition(int n) : g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {}
    void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); }
    void build() { dfs(0, -1); bfs(); }
    int dfs(int curr, int prev) {
        parent[curr] = prev; int sub = 1, max_sub = 0;
        for (int next : g[curr]) if (next != prev) {
            depth[next] = depth[curr] + 1; int sub_next = dfs(next, curr); sub += sub_next;
            if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next;
        }
        return sub;
    }
    void bfs() {
        int k = 0; queue<int> q({ 0 });
        while (!q.empty()) {
            int h = q.front(); q.pop();
            for (int i = h; i != -1; i = heavy[i]) {
                vid[i] = k++; inv[vid[i]] = i; head[i] = h;
                for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j);
            }
        }
    }

    void foreach(int u, int v, function<void(int, int)> f) {
        if (vid[u] > vid[v]) swap(u, v);
        f(max(vid[head[v]], vid[u]), vid[v]);
        if (head[u] != head[v]) foreach(u, parent[head[v]], f);
    }

    int ancestor(int u, int d) { // uのd個上の頂点を返す(無いなら0)
        while (true) {
            if (depth[head[u]] > depth[u] - d) {
                d -= depth[u] - depth[head[u]] + 1;
                if (head[u] == 0) return 0;
                u = parent[head[u]];
            }
            else return inv[vid[u] - d];
        }
    }

    int lca(int u, int v) {
        if (vid[u] > vid[v]) swap(u, v);
        if (head[u] == head[v]) return u;
        return lca(u, parent[head[v]]);
    }

    // 頂点 u と頂点 v の距離を求める
    int distance(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
};
//-----------------------------------------------------------------------------------
int N, A[101010]; vector<int> E[101010];
int chk(int a, int b, int c) {
    if (max(A[a], A[c]) < A[b] && A[a] != A[c]) return 1;
    if (A[b] < min(A[a], A[c]) && A[a] != A[c]) return 1;
    return 0;
}
//-----------------------------------------------------------------------------------
int cnt[101010];
void dfs(int cu, int pa, HLDecomposition &hld) {
    if (2 <= hld.depth[cu]) {
        int a = hld.ancestor(cu, 2);
        int b = hld.ancestor(cu, 1);
        int c = cu;

        cnt[cu] = chk(a, b, c);
    }

    for (int to : E[cu]) if (to != pa) dfs(to, cu, hld);
}
void dfs2(int cu, int pa = -1) {
    for (int to : E[cu]) if (to != pa) {
        cnt[to] += cnt[cu];
        dfs2(to, cu);
    }
}
//-----------------------------------------------------------------------------------
int main() {
    cin >> N; rep(i, 0, N) scanf("%d", &A[i]);

    HLDecomposition hld(N);
    rep(i, 0, N - 1) {
        int a, b; scanf("%d%d", &a, &b); a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
        hld.add(a, b);
    }
    hld.build();

    dfs(0, -1, hld);
    dfs2(0);

    int Q; cin >> Q;
    rep(q, 0, Q) {
        int a, b; scanf("%d%d", &a, &b); a--; b--;
        int p = hld.lca(a, b);

        bool ans = true;

        if (a == p) {
            int pb = hld.ancestor(b, hld.depth[b] - hld.depth[p] - 1);
            if (!chk(b, a, pb)) ans = false;

            int d = hld.depth[b] - hld.depth[p] - 1;
            if (0 < d) {
                int c = cnt[b] - cnt[hld.ancestor(b, d)];
                if (c != d) ans = false;
            }

            if (!chk(a, b, hld.ancestor(b, 1))) ans = false;
        }
        else if (b == p) {
            int pa = hld.ancestor(a, hld.depth[a] - hld.depth[p] - 1);
            if (!chk(a, b, pa)) ans = false;

            int d = hld.depth[a] - hld.depth[p] - 1;
            if (0 < d) {
                int c = cnt[a] - cnt[hld.ancestor(a, d)];
                if (c != d) ans = false;
            }

            if (!chk(hld.ancestor(a, 1), a, b)) ans = false;
        }
        else {
            int pa = hld.ancestor(a, hld.depth[a] - hld.depth[p] - 1);
            int pb = hld.ancestor(b, hld.depth[b] - hld.depth[p] - 1);
            if (!chk(pa, p, pb)) ans = false;

            int d = hld.depth[a] - hld.depth[p] - 1;
            if (0 < d) {
                int c = cnt[a] - cnt[hld.ancestor(a, d)];
                if (c != d) ans = false;
            }

            d = hld.depth[b] - hld.depth[p] - 1;
            if (0 < d) {
                int c = cnt[b] - cnt[hld.ancestor(b, d)];
                if (c != d) ans = false;
            }

            if (!chk(hld.ancestor(a, 1), a, b)) ans = false;
            if (!chk(a, b, hld.ancestor(b, 1))) ans = false;
        }

        if (ans) printf("YES\n");
        else printf("NO\n");
    }
}
0