結果

問題 No.363 門松サイクル
ユーザー mamekinmamekin
提出日時 2016-04-23 12:43:44
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 585 ms / 4,000 ms
コード長 4,732 bytes
コンパイル時間 1,425 ms
コンパイル使用メモリ 123,620 KB
実行使用メモリ 36,352 KB
最終ジャッジ日時 2024-04-19 07:21:18
合計ジャッジ時間 10,681 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 6 ms
6,944 KB
testcase_03 AC 5 ms
6,944 KB
testcase_04 AC 6 ms
6,944 KB
testcase_05 AC 7 ms
6,944 KB
testcase_06 AC 7 ms
6,944 KB
testcase_07 AC 7 ms
6,940 KB
testcase_08 AC 6 ms
6,940 KB
testcase_09 AC 203 ms
11,648 KB
testcase_10 AC 209 ms
11,392 KB
testcase_11 AC 392 ms
25,216 KB
testcase_12 AC 470 ms
22,272 KB
testcase_13 AC 418 ms
18,048 KB
testcase_14 AC 357 ms
17,024 KB
testcase_15 AC 352 ms
23,816 KB
testcase_16 AC 317 ms
19,328 KB
testcase_17 AC 585 ms
36,280 KB
testcase_18 AC 490 ms
18,932 KB
testcase_19 AC 412 ms
16,896 KB
testcase_20 AC 488 ms
18,304 KB
testcase_21 AC 584 ms
31,104 KB
testcase_22 AC 460 ms
17,920 KB
testcase_23 AC 499 ms
27,264 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 441 ms
36,352 KB
testcase_27 AC 437 ms
36,352 KB
testcase_28 AC 499 ms
26,368 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

class LowestCommonAncestor
{
private:
    vector<vector<int> > to;
    vector<int> depth;
public:
    LowestCommonAncestor()
    {}
    LowestCommonAncestor(const vector<vector<int> >& edges, int root)
    {
        int n = edges.size();
        to.assign(n, vector<int>());
        depth.resize(n);

        stack<tuple<int, int, int, int> > stk;
        stk.push(make_tuple(root, -1, 0, 0));
        while(!stk.empty()){
            int curr, prev, cnt, i;
            tie(curr, prev, cnt, i) = stk.top();
            stk.pop();

            if(i == 0){
                depth[curr] = cnt;
                if(prev != -1){
                    to[curr].push_back(prev);
                    int j = prev;
                    for(unsigned k=0; k<to[j].size(); ++k){
                        j = to[j][k];
                        to[curr].push_back(j);
                    }
                }
            }

            if(i < (int)edges[curr].size()){
                stk.push(make_tuple(curr, prev, cnt, i + 1));
                int next = edges[curr][i];
                if(next != prev)
                    stk.push(make_tuple(next, curr, cnt + 1, 0));
            }
        }
    }
    int climb(int curr, int dist)
    {
        int i = 0;
        while(dist > 0){
            if(dist % 2 == 1)
                curr = to[curr][i];
            dist /= 2;
            ++ i;
        }
        return curr;
    }
    // 2つのノードの最小共通祖先を取得
    int getAncestor(int a, int b)
    {
        int diff = depth[a] - depth[b];
        if(diff < 0)
            b = climb(b, -diff);
        else
            a = climb(a, diff);
        if(a == b)
            return a;

        for(int i=to[a].size()-1; i>=0; --i){
            if(i < (int)to[a].size() && to[a][i] != to[b][i]){
                a = to[a][i];
                b = to[b][i];
            }
        }
        return to[a][0];
    }
    // ノードの深さを取得
    int getDepth(int a)
    {
        return depth[a];
    }
    // 2つのノードの距離を取得
    int getDist(int a, int b)
    {
        int c = getAncestor(a, b);
        return getDepth(a) + getDepth(b) - getDepth(c) * 2;
    }
};

bool checkKadomatsu(const vector<int>& a)
{
    if(a[0] == a[2])
        return false;
    return (a[0] < a[1] && a[2] < a[1]) || (a[0] > a[1] && a[2] > a[1]);
}

int n;
vector<int> a;
vector<vector<int> > edges;
vector<int> cnt;
LowestCommonAncestor lca;

void dfs(int curr, int prev, int prev2)
{
    if(prev2 != -1 && checkKadomatsu({a[curr], a[prev], a[prev2]}))
        cnt[curr] = cnt[prev] + 1;
    for(int next : edges[curr]){
        if(next != prev)
            dfs(next, curr, prev);
    }
}

bool solve(int u, int v)
{
    if(lca.getDist(u, v) < 2)
        return false;

    int w = lca.getAncestor(u, v);
    int du = lca.getDist(u, w);
    int dv = lca.getDist(v, w);

    if(u == w || v == w){
        if(u == w){
            swap(u, v);
            swap(du, dv);
        }

        int u2 = lca.climb(u, du - 1);
        if(cnt[u] - cnt[u2] < du - 1)
            return false;

        int u3 = lca.climb(u, 1);
        return checkKadomatsu({a[u3], a[u], a[v]}) && checkKadomatsu({a[u], a[v], a[u2]});
    }
    else{
        int u2 = lca.climb(u, du - 1);
        if(cnt[u] - cnt[u2] < du - 1)
            return false;

        int v2 = lca.climb(v, dv - 1);
        if(cnt[v] - cnt[v2] < dv - 1)
            return false;

        if(!checkKadomatsu({a[u2], a[w], a[v2]}))
            return false;

        int u3 = lca.climb(u, 1);
        int v3 = lca.climb(v, 1);
        return checkKadomatsu({a[u3], a[u], a[v]}) && checkKadomatsu({a[u], a[v], a[v3]});
    }
}

int main()
{
    cin >> n;
    a.resize(n);
    for(int i=0; i<n; ++i)
        cin >> a[i];

    edges.assign(n, vector<int>());
    for(int i=0; i<n-1; ++i){
        int x, y;
        cin >> x >> y;
        -- x;
        -- y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    lca = LowestCommonAncestor(edges, 0);

    cnt.assign(n, 0);
    dfs(0, -1, -1);

    int q;
    cin >> q;
    while(--q >= 0){
        int u, v;
        cin >> u >> v;
        -- u;
        -- v;
        if(solve(u, v))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}
0