QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422106#8720. BFS 序 0MaxDYFML 2ms5616kbC++233.1kb2024-05-26 19:27:292024-05-26 19:27:30

Judging History

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

  • [2024-05-26 19:27:30]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:5616kb
  • [2024-05-26 19:27:29]
  • 提交

answer

// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int f[N][25];
vector<int> G[N];
int dep[N];
void dfs(int x)
{
    dep[1] = 1;
    for (int i = 1; i < 25; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (auto y : G[x])
    {
        f[y][0] = x;
        dep[y] = dep[x] + 1;
        dfs(y);
    }
}
int lca(int x, int y)
{
    if (x == y)
        return x;
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 24; i >= 0; i--)
        if (dep[f[x][i]] > dep[y])
            x = f[x][i];
    if (x == y)
        return x;
    for (int i = 24; i >= 0; i--)
        if (f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }
    return f[x][0];
}
vector<int> G1[N];
int jump(int x, int fa)
{
    int stp = dep[x] - dep[fa] - 1;
    for (int i = 24; i >= 0; i--)
    {
        if (stp & (1 << i))
            x = f[x][i];
    }
    return x;
}
bool vis[N];
void work()
{
    cin >> n;
    for (int y = 2; y <= n; y++)
    {
        int x;
        cin >> x;
        G[x].push_back(y);
    }
    dfs(1);
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> m;
        vector<int> arr(m), vec;
        auto clear = [&]() {
            for (auto x : vec)
            {
                G1[x].clear();
                vis[x] = 0;
            }
        };
        for (int i = 0; i < m; i++)
            cin >> arr[i];
        bool ok = 1;
        for (int i = 1; i < m; i++)
        {
            int x = arr[i - 1], y = arr[i];
            if (dep[x] > dep[y])
            {
                ok = 0;
                break;
            }
            if (dep[x] != dep[y])
                continue;
            int anc = lca(x, y);
            int x1 = jump(x, anc);
            int x2 = jump(y, anc);
            vec.push_back(x1);
            vec.push_back(x2);
            G1[x1].push_back(x2);
        }
        if (!ok)
        {
            cout << "No\n";
            clear();
            continue;
        }
        auto checkRing = [&](auto &checkRing, int x) {
            if (vis[x])
                return false;
            vis[x] = false;
            for (auto y : G1[x])
            {
                if (!checkRing(checkRing, y))
                    return false;
            }
            return true;
        };
        for (auto x : vec)
            if (ok && !vis[x] && !checkRing(checkRing, x))
            {
                ok = false;
                break;
            }
        cout << (ok ? "Yes\n" : "No\n");
        clear();
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t-- > 0)
    {
        work();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5616kb

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
Memory Limit Exceeded

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:


result: