QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#693593 | #8551. DFS Order 5 | sdmrlh | TL | 2ms | 15808kb | C++14 | 2.4kb | 2024-10-31 16:26:30 | 2024-10-31 16:26:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld%lld",&x,&y)
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pf(x) printf("%lld",x)
#define pii pair<int,int>
#define f first
#define s second
#define int long long
//
const int N = 1e5+10,M=2*N;
map<int,int> ve[N];
int h[N],e[M],ne[M],idx;
int si[N],q[M],depth[N],dis[N],fa[N][30];
int now[N],nn,bl;
//
void add(int a,int b)
{
ne[idx]=h[a],e[idx]=b,h[a]=idx++;
}
void no()
{
cout<<"No"<<endl;
bl=1;
}
void dfs(int u,int fa)
{
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
ve[u][j]=1;
dfs(j,u);
si[u]+=si[j];
}
}
void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[root] = 1;
int hh = 0, tt = 0;
q[0] = root;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q[ ++ tt] = j;
fa[j][0] = t;
for (int k = 1; k <= 15; k ++ )
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k -- )
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if (a == b) return a;
for (int k = 15; k >= 0; k -- )
if (fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}
bool panduan(vector<int> &c,int l,int r)
{
int now=c[l];
int nn = l;
while(nn!=r)
{
if(nn>r) return 0;
if(ve[now].count(c[nn+1]))
{
if(!panduan(c,nn+1,nn+si[c[nn+1]])) return 0;
nn = nn+si[c[nn+1]];
}
}
return 1;
}
//
void solve()
{
int m,n;
cin>>m>>n;
for(int i=1;i<=m;i++) h[i]=-1,si[i]=1;
for(int i=1;i<m;i++)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
dfs(1,-1);
bfs(1);
while(n--)
{
cin>>nn;
for(int i=1;i<=nn;i++) cin>>now[i];
int l=1,r = 1,last=-1;
while(l<=nn)
{
bl=0;
vector<int> c;
if(last!=-1&&(lca(now[1],now[l])==now[l]||lca(fa[last][0],fa[now[l]][0])!=fa[now[l]][0])){
no();
break;
}
r=l;
last=now[l];
for(int i=l;i<=min(nn,l+si[now[l]]-1);i++,r++)
c.push_back(now[i]);
l=r;
if(!panduan(c,0,c.size()-1)) {
no();
break;
}
}
if(!bl) cout<<"Yes"<<endl;
}
}
signed main()
{
IOS;
int _=1;
while(_--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 15808kb
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: -100
Time Limit Exceeded
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 ...