QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#455454	#8720. BFS 序 0	Andyqian7	WA	276ms	74356kb	C++14	2.8kb	2024-06-26 14:26:17	2024-06-26 14:26:17

Judging History

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

[2024-06-26 14:26:17]
评测

测评结果：WA
用时：276ms
内存：74356kb

查看

[2024-06-26 14:26:17]
提交

answer

#include <bits/stdc++.h>
#define lowbit(x) x & -x
using namespace std;
const int MAX = 5e5 + 10;
int n, T, m, dep[MAX], q[MAX], f[MAX][20], deg[MAX], vis[MAX];
vector<int> sons[MAX];
set<int> nxt[MAX];
int anc(int s, int dis)
{
    int ans = 0;
    for (int i = 0; i < 20; i++)
    {
        if (dis >> i & 1)
            ans = f[s][i];
    }
    return ans;
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    x = anc(x, dep[x] - dep[y]);
    for (int i = 19; ~i; i--)
    {
        if (f[x][i] != f[y][i])
        {
            x = f[x][i], y = f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    cin >> n;
    for (int i = 2; i <= n; i++)
    {
        int fa;
        cin >> fa;
        sons[fa].push_back(i), dep[i] = dep[fa] + 1, f[i][0] = fa;
    }
    for (int i = 0; i < 19; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            f[j][i + 1] = f[f[j][i]][i];
        }
    }
    cin >> T;
    while (T--)
    {
        cin >> m;
        vector<int> c;
        for (int i = 1; i <= m; i++)
        {
            cin >> q[i];
            c.push_back(q[i]);
        }
        sort(c.begin(), c.end());
        int sz = c.size();
        if (unique(c.begin(), c.end()) - c.begin() != sz)
        {
            cout << "No" << endl;
            continue;
        }
        set<int> todo;
        bool sign = true;
        for (int i = 1; i < m; i++)
        {
            if (dep[q[i]] > dep[q[i + 1]])
            {
                cout << "No" << endl;
                sign = false;
                break;
            }
        }
        if (!sign)
            continue;
        for (int i = 1; i < m; i++)
        {
            if (dep[q[i]] == dep[q[i + 1]])
                continue;
            int z = lca(q[i], q[i + 1]);
            int a = anc(q[i], dep[q[i]] - dep[z] - 1);
            int b = anc(q[i + 1], dep[q[i + 1]] - dep[z] - 1);
            nxt[a].insert(b);
            deg[b]++;
            todo.insert(a), todo.insert(b);
        }
        queue<int> Q;
        for (int s : todo)
        {
            if (!deg[s])
                Q.push(s);
        }
        while (Q.size())
        {
            int t = Q.front();
            vis[t] = 1;
            Q.pop();
            for (int son : nxt[t])
            {
                deg[son]--;
                if (!deg[son])
                    Q.push(son);
            }
        }
        for (int s : todo)
        {
            nxt[s].clear();
            deg[s] = 0;
            if (!vis[s])
            {
                cout << "No" << endl;
                sign = false;
            }
            vis[s] = 0;
        }
        if (sign)
            cout << "Yes" << endl;
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 45396kb

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: 276ms

memory: 74356kb

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:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

wrong answer expected YES, found NO [2nd token]