結果

問題 No.363 門松サイクル
ユーザー 👑 はまやんはまやんはまやんはまやん
提出日時 2017-04-22 05:07:00
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 174 ms / 4,000 ms
コード長 5,016 bytes
コンパイル時間 1,964 ms
コンパイル使用メモリ 178,304 KB
実行使用メモリ 25,136 KB
最終ジャッジ日時 2023-09-28 12:22:26
合計ジャッジ時間 7,351 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,976 KB
testcase_01 AC 4 ms
5,888 KB
testcase_02 AC 5 ms
5,904 KB
testcase_03 AC 5 ms
6,020 KB
testcase_04 AC 4 ms
5,996 KB
testcase_05 AC 4 ms
6,016 KB
testcase_06 AC 5 ms
5,988 KB
testcase_07 AC 4 ms
5,916 KB
testcase_08 AC 4 ms
6,092 KB
testcase_09 AC 54 ms
11,576 KB
testcase_10 AC 62 ms
11,836 KB
testcase_11 AC 125 ms
20,272 KB
testcase_12 AC 130 ms
18,964 KB
testcase_13 AC 141 ms
16,412 KB
testcase_14 AC 102 ms
15,532 KB
testcase_15 AC 112 ms
19,256 KB
testcase_16 AC 80 ms
15,760 KB
testcase_17 AC 154 ms
25,032 KB
testcase_18 AC 174 ms
17,532 KB
testcase_19 AC 121 ms
18,784 KB
testcase_20 AC 168 ms
17,344 KB
testcase_21 AC 159 ms
23,188 KB
testcase_22 AC 143 ms
17,136 KB
testcase_23 AC 111 ms
20,528 KB
testcase_24 AC 3 ms
5,808 KB
testcase_25 AC 3 ms
5,804 KB
testcase_26 AC 91 ms
24,928 KB
testcase_27 AC 92 ms
25,136 KB
testcase_28 AC 105 ms
21,172 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