QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#603057#8720. BFS 序 0lllei#WA 584ms96576kbC++205.1kb2024-10-01 14:26:502024-10-01 14:26:51

Judging History

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

  • [2024-10-01 14:26:51]
  • 评测
  • 测评结果:WA
  • 用时:584ms
  • 内存:96576kb
  • [2024-10-01 14:26:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
struct seg {
    int l, r;
};
seg merge(seg t1, seg t2) {
    t1.l = min(t1.l, t2.l);
    t1.r = max(t1.r, t2.r);
    return t1;
}
bool involve(seg t1, seg t2) {
    if (t1.l > t2.r || t2.l > t1.r)
        return false;
    return true;
}
struct s {
    map<int, seg> p;
    vector<int> lay;
    int siz;
} node[N];
int belon[N];
bool check(int t1, int t2) {
    int flag2 = 0;
    int tmp = node[t2].lay.size();
    for (int i = 0; i < tmp; i++) {
        int now = node[t2].lay[i];
        if (node[t1].p.contains(now)) {
            seg tmp1 = node[t1].p[now], tmp2 = node[t2].p[now];
            if (involve(tmp1, tmp2))
                return false;
            if (tmp1.l < tmp2.l) {
                if (flag2) {
                    if (flag2 == 2)
                        return false;
                } else
                    flag2 = 1;
            } else {
                if (flag2) {
                    if (flag2 == 1)
                        return false;
                } else
                    flag2 = 2;
            }
        }
    }
    return true;
}
bool mergenode(int t1, int t2) { // t1<-t2
    int tmp1 = belon[t1], tmp2 = belon[t2];
    if (node[tmp1].siz < node[tmp2].siz)
        swap(tmp1, tmp2);
    belon[t1] = tmp1;
    bool flag1 = check(tmp1, tmp2);
    int tmp = node[tmp2].lay.size();
    for (int i = 0; i < tmp; i++) {
        int now = node[tmp2].lay[i];
        if (!node[tmp1].p.contains(now)) {
            node[tmp1].p[now] = node[tmp2].p[now];
            node[tmp1].lay.push_back(now);
        } else
            node[tmp1].p[now] = merge(node[tmp1].p[now], node[tmp2].p[now]);
    }
    return flag1;
}

int n, fa[N], m, q, pa[N][22];
int dep[N];
int id[N];
int lca(int t1, int t2) {
    if (dep[t1] > dep[t2])
        swap(t1, t2);
    for (int i = 20; i >= 0; i--)
        if (dep[pa[t2][i]] >= dep[t1])
            t2 = pa[t2][i];
    if (t1 == t2)
        return t1;
    for (int i = 20; i >= 0; i--)
        if (pa[t1][i] != pa[t2][i]) {
            t1 = pa[t1][i];
            t2 = pa[t2][i];
        }
    return pa[t1][0];
}
vector<int> son[N];
int dfn[N], tme = 0;
int faa[N]; // xushu
void dfs(int now) {
    dfn[now] = ++tme;
    int tmp = son[now].size();
    for (int i = 0; i < tmp; i++)
        dfs(son[now][i]);
    return;
}
int bfn[N], rak[N];
vector<int> b;
bool ss(int t1, int t2) {
    return dfn[t1] < dfn[t2];
}
int sonnum[N];
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> fa[i];
        son[fa[i]].push_back(i);
    }
    dfs(1);
    for (int i = 1; i <= n; i++)
        pa[i][0] = fa[i];
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++)
            pa[j][i] = pa[pa[j][i - 1]][i - 1];
    dep[1] = 1;
    for (int i = 2; i <= n; i++)
        dep[i] = dep[fa[i]] + 1;
    cin >> q;
    while (q--) {
        cin >> m;
        for (int i = 1; i <= m; i++) {
            cin >> bfn[i];
            rak[bfn[i]] = i;
            id[i] = bfn[i];
        }
        sort(id + 1, id + m + 1, ss);
        bool flag = true;
        for (int i = 2; i <= m; i++)
            if (dep[bfn[i]] < dep[bfn[i - 1]]) {
                flag = false;
                break;
            }
        for (int i = 1; i < m; i++) {
            int now = lca(id[i], id[i + 1]);
            node[now].p.clear();
            node[now].siz = 0;
            node[now].lay.clear();
            belon[now] = now;
        }
        for (int i = 1; i <= m; i++) {
            node[bfn[i]].p.clear();
            node[bfn[i]].lay.clear();
            seg tmp1;
            tmp1.l = tmp1.r = i;
            node[bfn[i]].p[dep[i]] = tmp1;
            node[bfn[i]].siz = 1;
            belon[bfn[i]] = bfn[i];
            node[bfn[i]].lay.push_back(dep[bfn[i]]);
        }

        b.clear();
        b.push_back(1);
        for (int i = 1; i <= m; i++) {
            b.push_back(id[i]);
            if (i != m)
                b.push_back(lca(id[i], id[i + 1]));
        }
        b.erase(unique(b.begin(), b.end()), b.end());
        int tmp = b.size();
        for (int i = 0; i < tmp; i++)
            sonnum[b[i]] = 0;
        for (int i = 0; i < tmp - 1; i++) {
            int lcaa = lca(b[i], b[i + 1]);
            faa[b[i + 1]] = lcaa;
            sonnum[lcaa]++;
        }
        queue<int> q;
        for (int i = 0; i < tmp; i++)
            if (sonnum[b[i]] == 0)
                q.push(b[i]);
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            if (!mergenode(now, faa[now]))
                flag = false;
            sonnum[faa[now]]--;
            if (sonnum[faa[now]] == 0)
                q.push(faa[now]);
        }
        if (flag)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

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

詳細信息

Test #1:

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

input:

6
1 1 3 2 4
10
4 3 6 2 5
1 4
3 2 4 5
5 2 5 4 6 3
3 1 4 2
3 5 6 3
5 4 5 2 6 1
4 4 3 2 5
4 4 6 2 3
3 3 2 6

output:

No
Yes
Yes
No
No
No
No
No
No
Yes

result:

ok 10 token(s): yes count is 3, no count is 7

Test #2:

score: -100
Wrong Answer
time: 584ms
memory: 96576kb

input:

300000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

wrong answer expected NO, found YES [1st token]