QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#536363#8551. DFS Order 5QSteve_PaulRE 0ms65492kbC++237.3kb2024-08-29 08:53:432024-08-29 08:53:43

Judging History

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

  • [2024-08-29 08:53:43]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:65492kb
  • [2024-08-29 08:53:43]
  • 提交

answer

#include <vector>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;

struct SegmentTree
{
    constexpr static int N = 1e6 + 5;

#define rson ((k << 1) + 1)
#define lson (k << 1)
#define me (k)
#define mid ((a[me].l + a[me].r) >> 1)

    struct node
    {
        int l, r;
        int sum;
        int lazy;

        node()
        {
            l = r = sum = 0;
            lazy = -1;
        }
    };

    vector<node> a = vector<node>(N * 4);

    void update(int k)
    {
        a[me].sum = a[lson].sum + a[rson].sum;
    }

    void build(int k, int l, int r)
    // 当前在k上,建树
    {
        a[me].l = l;
        a[me].r = r;
        if (l == r)
        {
            a[me].sum = 0;
            return;
        }
        build(lson, a[me].l, mid);
        build(rson, mid + 1, a[me].r);
        update(k);
    }

    void pushdown(int k)
    {
        if (a[me].l == a[me].r)
        {
            a[me].lazy = -1;
            return;
        }
        a[lson].sum = (a[lson].r - a[lson].l + 1) * a[me].lazy;
        a[rson].sum = (a[rson].r - a[rson].l + 1) * a[me].lazy;
        a[lson].lazy = a[me].lazy;
        a[rson].lazy = a[me].lazy;
        a[me].lazy = -1;
    }

    int query(int k, int idx)
    {
        if (a[me].lazy != -1)
            pushdown(k);
        if (a[me].l == idx && a[me].r == idx)
            return a[me].sum;
        if (idx <= mid)
            return query(lson, idx);
        return query(rson, idx);
    }

    void set_segment(int k, int l, int r, int x)
    {
        if (a[k].l == l && a[k].r == r)
        {
            a[k].sum = (r - l + 1) * x;
            a[k].lazy = x;
            return;
        }
        if (a[me].lazy != -1)
            pushdown(k);
        if (r <= mid)
            set_segment(lson, l, r, x);
        else if (l > mid)
            set_segment(rson, l, r, x);
        else
        {
            set_segment(lson, l, mid, x);
            set_segment(rson, mid + 1, r, x);
        }
        update(k);
    }
#undef rson
#undef lson
#undef me
#undef mid
};

void solve()
{
    int n;
    cin >> n;
    int q;
    cin >> q;
    SegmentTree st;
    st.build(1, 1, n);
    vector<vector<int>> tree(n + 1);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        tree[u].emplace_back(v);
        tree[v].emplace_back(u);
    }
    tree[1].emplace_back(0);


    vector<int> dfn(n + 1);
    vector<int> ofn(n + 1);
    vector<int> sz(n + 1);
    vector<int> ffa(n + 1);
    vector<int> depth(n + 1);
    vector<int> hvy(n + 1);
    vector<int> hvymn(n + 1);
    vector<int> hvymx(n + 1);
    vector<int> hvyid(n + 1, -1);


    function<void(int, int)> dfs1 = [&](int node, int fa) -> void
    {
        depth[node] = depth[fa] + 1;
        ffa[node] = fa;
        sz[node] = 1;
        for (const int& child : tree[node])
        {
            if (child == fa) continue;
            dfs1(child, node);
            sz[node] += sz[child];
        }
    };

    dfs1(1, 0);

    for (int i = 1; i <= n; i++)
    {
        int idx = 0;
        int mx = -1;
        for (const int& child : tree[i])
        {
            ++idx;
            if (child == ffa[i]) continue;
            if (mx == -1) mx = child;
            else
            {
                if (sz[child] > sz[mx])
                    mx = child;
            }
        }
        if(mx != -1)
            hvy[mx] = 1;
        hvyid[i] = mx;
    }

    int dfncnt = 0;
    function<void(int, int)> dfs2 = [&](int node, int fa) -> void
    {
        dfncnt++;
        dfn[node] = dfncnt;
        if (hvy[node])
        {
            if (hvy[fa])
                hvymn[node] = hvymn[fa];
            else
                hvymn[node] = dfn[node];
            hvymx[node] = dfn[node];
        }
        if (hvyid[node] != -1)
        {
            dfs2(hvyid[node], node);
            hvymx[node] = hvymx[hvyid[node]];
        }
        for (const int& child : tree[node])
        {
            if (child == fa) continue;
            if (child == hvyid[node]) continue;
            dfs2(child, node);
        }
        ofn[node] = dfncnt;
    };

    dfs2(1, 0);

    for (int i = 1; i <= n; i++)
    {
        int faidx = -1;
        for (int j = 0; j < tree[i].size(); j++)
            if (ffa[i] == tree[i][j])
                faidx = j;
        if(faidx != -1)
            swap(tree[i][faidx], tree[i].back());
        tree[i].pop_back();
        sort(tree[i].begin(), tree[i].end(), [&](const int& nd1, const int& nd2)
        {
            return ofn[nd1] < ofn[nd2];
        });
    }

    function<bool(int, int)> is_in_tree = [&](int node, int fa) -> bool
    {
        return dfn[node] >= dfn[fa] && dfn[node] <= ofn[fa];
    };

    function<void(int)> add_line = [&](int node) -> void
    {
        while (node != 0)
        {
            if (hvy[node])
            {
                int mn = hvymn[node];
                st.set_segment(1, dfn[mn], dfn[node], 1);
                node = mn;
            }
            else
            {
                st.set_segment(1, dfn[node], dfn[node], 1);
            }
            node = ffa[node];
        }
    };

    vector<int> k;
    while (q--)
    {
        int qq;
        cin >> qq;
        k.resize(qq + 1);
        for (int i = 1; i <= qq; i++)
            cin >> k[i];

        // TODO: clear the SegmentTree
        st.set_segment(1, 1, n, 0);


        bool isok = true;
        if (!is_in_tree(k[min(1 + sz[k[1]] - 1, qq)], k[1]))
            isok = false;
        add_line(k[1]);

        for (int i = 2; i <= qq; i++)
        {
            if (!is_in_tree(k[min(i + sz[k[i]] - 1, qq)], k[i])) isok = false;
            if (!isok) break;
            int thisfa = ffa[k[i]];
            if (!is_in_tree(k[i - 1], thisfa)) isok = false;
            if (!isok) break;

            // TODO: ensure it's not visited in SegmentTree
            if (st.query(1, dfn[k[i]]))
                isok = false;
            if (!isok) break;

            add_line(k[i]);

            if (thisfa != k[i - 1])
            {
                if (dfn[k[i-1]] < dfn[tree[thisfa].front()] || dfn[k[i-1]] > ofn[tree[thisfa].back()]) isok = false;
                if (!isok) break;

                int l = 0;
                int r = tree[thisfa].size() - 1;
                while (l < r)
                {
                    int mid = (l + r) / 2 ;
                    if (ofn[tree[thisfa][mid]] < dfn[k[i-1]]) l = mid + 1;
                    else r = mid;
                }

                int nearfa = tree[thisfa][l];
                if(!is_in_tree(k[i-1], nearfa)) isok = false;
                if(!isok) break;
                // TODO: ensure the childs of nearfa and itself is visited
                st.set_segment(1, dfn[nearfa], ofn[nearfa], 1);
            }
        }

        if (isok) cout << "Yes\n";
        else cout << "No\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

/*
*
6 4
1 2
1 3
2 4
3 5
2 6
3 4 6 3
3 4 6 1
4 2 6 4 3
4 1 4 6 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 65492kb

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
Runtime Error

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:


result: