QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491404 | #8551. DFS Order 5 | ucup-team2307# | WA | 54ms | 5604kb | C++23 | 2.7kb | 2024-07-25 19:19:02 | 2024-07-25 19:19:03 |
Judging History
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'