QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#576840#8551. DFS Order 5ucup-team4435#WA 97ms3644kbC++2010.5kb2024-09-19 22:50:522024-09-19 22:50:53

Judging History

你现在查看的是最新测评结果

  • [2024-09-19 22:50:53]
  • 评测
  • 测评结果:WA
  • 用时:97ms
  • 内存:3644kb
  • [2024-09-19 22:50:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

#ifdef LOCAL
    #include "debug.h"
#else
    #define dbg(...)
    #define dprint(...)
    #define debug if constexpr (false)
    #define draw_tree(...)
    #define draw_array(...)
#endif // LOCAL

template<typename Fun>
struct y_combinator {
    const Fun fun;

    explicit y_combinator(const Fun&& fun) : fun(std::forward<const Fun>(fun)) {}

    template<typename... Args>
    auto operator()(Args&&... args) const {
        return fun(std::ref(*this), std::forward<Args>(args)...);
    }
};

/*
 * Zero based.
 * Type T must have operator += T.
 * Type T must have default constructor, which sets neutral value.
 * Operation += must be commutative.
 * For segment query type T must have operator -= T.
 */
template<typename T>
struct binary_indexed_tree {
    std::vector<T> bit;

    // Fills the array with default values.
    binary_indexed_tree(int n = 0) : bit(n + 1) {}

    int size() const {
        return int(bit.size()) - 1;
    }

    // Adds delta at the position pos.
    void add(int pos, T delta) {
        for (pos++; pos < static_cast<int>(bit.size()); pos += pos & -pos) {
            bit[pos] += delta;
        }
    }

    // Returns the sum on the segment [0, pref].
    T query(int pref) {
        T sum = T();
        for (pref++; pref > 0; pref -= pref & -pref) {
            sum += bit[pref];
        }
        return sum;
    }

    // Returns the sum on the interval [l, r).
    T query(int l, int r) {
        if (r <= l) {
            return T();
        }
        T res = query(r - 1);
        res -= query(l - 1);
        return res;
    }
};

/*
 * Zero based.
 * Works for operations Op, such that Op(S) = Op(S \cup x), where x in S (like min, max, gcd...).
 * Operation must be commutative.
 */
template<typename T, typename merge_t = std::function<T(T, T)>>
class sparse_table {
private:
    std::vector<std::vector<T>> sparse;
    const merge_t merge;

public:
    sparse_table(const merge_t &merge) : merge(merge) {}

    sparse_table(const std::vector<T> &a, const merge_t &merge) : merge(merge) {
        const int n = a.size(), lg = std::__lg(std::max(1, n));
        sparse.reserve(lg + 1);
        sparse.push_back(a);
        for (int level = 1; level <= lg; level++) {
            sparse.push_back(std::vector<T>(n - (1 << level) + 1));
            for (int i = 0; i < static_cast<int>(sparse[level].size()); i++) {
                sparse[level][i] = merge(sparse[level - 1][i], sparse[level - 1][i + (1 << (level - 1))]);
            }
        }
    }

    sparse_table(const sparse_table &sparse) : sparse(sparse.sparse), merge(sparse.merge) {}

    sparse_table& operator=(const sparse_table<T, merge_t> &another) {
        sparse = another.sparse;
        return *this;
    }

    // Returns result of merging elements on the interval [l, r).
    T query(int l, int r) const {
        assert(l < r);
        const int level = std::__lg(r - l);
        return merge(sparse[level][l], sparse[level][r - (1 << level)]);
    }
};

/*
 * Include sparse_table to use it.
 * Zero based.
 * Type T is the type of the weight of each edge (int by default).
 * Don't forget to run .build(root) method before using it.
*/
 
template<typename T = int>
struct lca_tree {
    int n;
    std::vector<std::vector<std::pair<int, T>>> g;
    std::vector<int> tin, tout, parent;
    std::vector<std::pair<int, int>> order;
    std::vector<T> depth;
 
    inline static auto merge_min = [](const std::pair<int, int> &a, const std::pair<int, int> &b) -> std::pair<int, int> {
        return a < b ? a : b;
    };
    using sparse_table_t = sparse_table<std::pair<int, int>, decltype(merge_min)>;
    sparse_table_t sparse;
 
    lca_tree(int n = 0) : n(n), g(n), sparse(merge_min) {}
 
    lca_tree(const std::vector<std::vector<std::pair<int, T>>> &graph) :
        n(graph.size()), g(graph), sparse(merge_min)
    {}
 
    lca_tree(const std::vector<std::vector<int>> &graph) : n(graph.size()), g(n), sparse(merge_min) {
        for (int v = 0; v < int(graph.size()); v++) {
            g[v].reserve(graph[v].size());
            for (int u : graph[v])
                g[v].emplace_back(u, 1);
        }
    }
 
    lca_tree(int n, const std::vector<std::pair<int, int>> &edges) : n(n), g(n), sparse(merge_min) {
        for (const auto &[v, u] : edges)
            add(v, u);
    }

    lca_tree(const lca_tree<T> &lca) :
        n(lca.n), g(lca.g), tin(lca.tin), tout(lca.tout), order(lca.order), depth(lca.depth), sparse(lca.sparse)
    {}
 
    // Adding edge (v, u) with weight w (1 by default).
    void add(int v, int u, T w = 1) {
        g[v].emplace_back(u, w);
        g[u].emplace_back(v, w);
    }
 
    int size() const {
        return n;
    }
 
    // Init function.
    void build(int root = 0) {
        tin.resize(n);
        tout.resize(n);
        parent.assign(n, -1);
        order.clear();
        order.reserve(n - 1);
        depth.resize(n);
        int timer = 0;
 
        std::function<void(int, int)> dfs = [&](int v, int dep) {
            tin[v] = timer++;
            for (auto &[u, w] : g[v]) {
                if (u == parent[v])
                    continue;
 
                parent[u] = v;
                depth[u] = depth[v] + w;
                order.emplace_back(dep, v);
                dfs(u, dep + 1);
            }
            tout[v] = timer;
        };
        dfs(root, 0);
 
        sparse = sparse_table_t(order, merge_min);
    }
 
    int lca(int v, int u) const {
        if (v == u)
            return v;
        
        auto [l, r] = std::minmax(tin[v], tin[u]);
        return sparse.query(l, r).second;
    }
 
    T dist(int v, int u) const {
        return depth[v] - 2 * depth[lca(v, u)] + depth[u];
    }
 
    // Returns true if v == u or v is ancestor of u.
    bool is_ancestor(int v, int u) const {
        return tin[v] <= tin[u] && tout[u] <= tout[v];
    }
};

/*
 * Include lca_tree to use it.
 * Zero based.
 * Type T is the type of the weight of each edge (int by default).
 * The constructor gets lca_tree with .build(root) method runned.
*/

template<typename T = int>
struct compressed_tree {
    lca_tree<T> lca;
    std::vector<std::vector<pair<int, T>>> g;
    std::vector<int> used_vertexes;

    compressed_tree(const lca_tree<T> &lca = lca_tree<T>()) : lca(lca), g(lca.size()) {}

    // Gets vertexes of the compressed tree.
    // Stores all used vertexes in used_vertexes.
    // For every used vertexes stores its adjacent vertexes.
    // Returns the root of the compressed tree (or -1 if it is empty).
    int build(std::vector<int> vertexes) {
        for (auto v : used_vertexes)
            g[v].clear();

        used_vertexes.clear();

        auto compare_tin = [&](int v, int u) {
            return lca.tin[v] < lca.tin[u];
        };
        std::sort(vertexes.begin(), vertexes.end(), compare_tin);

        int n_vertexes = vertexes.size();
        for (int i = 0; i + 1 < n_vertexes; i++)
            vertexes.push_back(lca.lca(vertexes[i], vertexes[i + 1]));

        std::sort(vertexes.begin(), vertexes.end(), compare_tin);
        vertexes.resize(std::unique(vertexes.begin(), vertexes.end()) - vertexes.begin());

        auto add = [&](int v, int u) {
            g[v].emplace_back(u, lca.depth[u] - lca.depth[v]);
            g[u].emplace_back(v, lca.depth[u] - lca.depth[v]);
        };

        std::vector<int> current_path;
        for (auto v : vertexes) {
            while (!current_path.empty() && !lca.is_ancestor(current_path.back(), v))
                current_path.pop_back();
            
            if (!current_path.empty())
                add(current_path.back(), v);
            
            current_path.push_back(v);
        }

        used_vertexes.swap(vertexes);
        return current_path.empty() ? -1 : current_path.front();
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    lca_tree lca(n);
    for (int i = 1, v, u; i < n; i++) {
        cin >> v >> u;
        v--, u--;
        lca.add(v, u);
    }
    lca.build(0);

    binary_indexed_tree<int> bit(n);
    compressed_tree ctree(lca);
    vector<int> used(n, -1), index(n);

    for (int timer = 0; timer < q; timer++) {
        int sz;
        cin >> sz;
        vector<int> ord(sz);
        for (auto &v : ord) {
            cin >> v;
            v--;
            used[v] = timer;
            bit.add(lca.tin[v], 1);
        }
        for (int i = 0; i < sz; i++) {
            index[ord[i]] = i;
        }

        bool result = [&]() -> bool {
            int root = ctree.build(ord);
            vector<int> builded_ord;
            bool fail = false;

            y_combinator([&](auto dfs, int v, bool last) -> int {
                builded_ord.push_back(v);

                sort(all(ctree.g[v]), [&](pair<int, int> left, pair<int, int> right) {
                    int v = left.first, u = right.first;
                    if (used[u] != timer) {
                        return false;
                    }
                    if (used[v] != timer) {
                        return true;
                    }
                    return index[v] < index[u];
                });

                int subtree = 1;
                for (int i = 0; i < len(ctree.g[v]); i++) {
                    auto [u, l] = ctree.g[v][i];
                    if (l > 1) {
                        builded_ord.push_back(-1);
                    }
                    ctree.g[u].erase(find(all(ctree.g[u]), make_pair(v, l)));
                    subtree += dfs(u, last && i == len(ctree.g[v]) - 1);
                }

                if (!last && used[v] == timer && bit.query(lca.tin[v], lca.tout[v]) != subtree) {
                    fail = true;
                }
                return subtree;
            })(root, true);

            if (fail || len(builded_ord) < sz) {
                return false;
            }
            for (int i = 0; i < sz; i++) {
                if (builded_ord.rbegin()[i] != ord.rbegin()[i]) {
                    return false;
                }
            }
            return true;
        }();

        cout << (result ? "Yes" : "No") << '\n';

        for (auto v : ord) {
            bit.add(lca.tin[v], -1);
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3548kb

input:

6 7
1 2
1 3
2 4
3 5
2 6
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
6 1 2 6 4 3 5

output:

No
No
Yes
No
No
Yes
Yes

result:

ok 7 tokens

Test #2:

score: -100
Wrong Answer
time: 97ms
memory: 3644kb

input:

10 100000
7 2
1 7
7 10
8 6
8 7
1 3
4 5
9 5
5 8
8 8 9 7 2 8 1 6 1
4 8 3 5 2
6 7 10 3 9 9 1
1 1
8 10 3 2 9 3 8 7 3
7 5 6 2 8 5 9 1
6 3 4 6 2 1 3
5 8 9 2 4 9
1 3
2 1 5
5 8 5 1 7 9
10 5 2 9 2 6 4 10 6 3 8
3 4 5 8
2 8 4
9 4 10 1 2 4 3 3 6 3
1 3
6 1 1 6 8 3 1
3 7 3 2
3 9 1 5
4 3 7 8 10
9 4 2 3 10 2 5 4 3 ...

output:

No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No...

result:

wrong answer 20th words differ - expected: 'No', found: 'Yes'