QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491404#8551. DFS Order 5ucup-team2307#WA 54ms5604kbC++232.7kb2024-07-25 19:19:022024-07-25 19:19:03

Judging History

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

  • [2024-07-25 19:19:03]
  • 评测
  • 测评结果:WA
  • 用时:54ms
  • 内存:5604kb
  • [2024-07-25 19:19:02]
  • 提交

answer

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second

typedef long long ll;
#define int ll

using namespace std;

const int N = 1e5+100;
const int K = 20;
vector<int> g[N];
int pr[N][K];
int dep[N];
void dfs(int v, int p, int d = 0)
{
    dep[v] = d;
    pr[v][0] = p;
    for (int i : g[v])
        if (i != p)
            dfs(i, v, d+1);
}

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

set<int> alrV;
map<int, int> down;
map<int, int> extradown;
bool dfs_check(int v)
{
    if (alrV.count(v))
        return true;
    alrV.insert(v);
    if (down[v]+extradown[v]+1 < int(g[v].size()))
        return false;
    for (int i : g[v])
        if (i != pr[v][0])
            if (!dfs_check(i))
                return false;
    return true;
}

bool ask(vector<int> qur)
{
    down.clear();
    extradown.clear();
    alrV.clear();
    set<pair<int, int> > alr;
    int s = qur[0];
    for (int i=1; i<int(qur.size()); i++)
    {
        int v = qur[i];
        if (v == 1)
            return false;
        if (g[s].size() > 1)
        {
            if (pr[v][0] != s)
                return false;
            if (alr.count({s, v}))
                return false;
            alr.insert({s, v});
            down[s]++;
            s = v;
        }
        else
        {
            for (int i=K-1; i>=0; i--)
                if (dep[pr[s][i]] >= dep[v])
                    s = pr[s][i];
            int sup = pr[s][0];
            extradown[sup]++;
            if (pr[v][0] != sup)
                return false;
            alr.insert({sup, s});
            if (alr.count({sup, v}))
                return false;
            alr.insert({sup, v});
            s = v;
        }
    }
    s = qur.back();
    for (int i=0; i-2<int(qur.size()); i++)
    {
        alrV.insert(s);
        s = pr[s][0];
    }
//    for (auto pa : down)
//        cout<<pa.fi<<" "<<pa.se+extradown[pa.fi]<<"\n";
    for (auto [v, x] : down)
        if (!dfs_check(v))
            return false;
    return true;
}
void solve()
{
    int m;
    cin>>m;
    vector<int> v(m);
    for (int& i : v)
        cin>>i;
    if (ask(v))
        cout<<"Yes\n";
    else
        cout<<"No\n";
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin>>n>>q;
    for (int i=1; i<n; i++)
    {
        int x, y;
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1, 1);
    for (int i=0; i+1<K; i++)
        for (int v=1; v<=n; v++)
            pr[v][i+1] = pr[v][pr[v][i]];
    while (q--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 32ms
memory: 3624kb

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
No
No
No
No
No
No
No
No
No
No
No
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
N...

result:

ok 100000 tokens

Test #3:

score: 0
Accepted
time: 54ms
memory: 5604kb

input:

20 95326
19 7
11 14
15 14
6 12
14 13
2 9
1 15
4 7
16 14
13 10
13 17
13 20
10 5
16 18
7 6
9 11
3 2
12 16
2 8
17 11 3 20 16 6 1 6 11 3 14 6 6 17 4 20 10 2
14 19 8 6 12 8 8 12 20 1 5 3 18 12 13
13 16 3 8 12 13 6 19 18 5 8 14 19 15
3 8 11 16
9 18 19 2 19 2 17 16 7 10
3 18 11 13
1 12
19 10 5 20 4 6 17 18...

output:

No
No
No
No
No
No
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
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No...

result:

ok 95326 tokens

Test #4:

score: -100
Wrong Answer
time: 47ms
memory: 3560kb

input:

30 64393
17 20
17 6
29 13
26 9
11 13
17 5
12 27
5 1
25 28
3 20
28 13
19 29
22 14
21 13
18 10
3 4
30 27
15 21
21 23
8 10
21 24
27 14
9 7
28 16
7 3
2 7
7 27
3 18
29 27
15 14 2 24 21 24 24 22 6 5 12 12 4 20 26 28
22 22 14 7 30 19 13 16 29 9 18 14 14 14 4 8 14 25 11 6 25 22 11
28 10 10 7 1 22 7 6 14 12 ...

output:

No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
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
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
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
No
No
No
No
N...

result:

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