QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693933 | #8551. DFS Order 5 | szy10010 | WA | 7ms | 36448kb | C++23 | 3.2kb | 2024-10-31 16:59:06 | 2024-10-31 16:59:14 |
Judging History
answer
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int h[N],e[N],ne[N],idx;
int depth[N],fa[N][20],sz[N],son[N];
int tr[N+10];//c[N];
int query(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))res+=tr[i];
return res;
}
void addtree(int x,int c)
{
for(int i=x;i<=N;i+=lowbit(i))tr[i]+=c;
}
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void bfs(int root)
{
memset(depth,0x3f,sizeof(depth));
depth[0]=0;
depth[root]=1;
queue<int>q;
q.push(root);
while(q.size())
{
auto t=q.front();
q.pop();
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.push(j);
fa[j][0]=t;
for(int i=1;i<=19;i++)
fa[j][i]=fa[fa[j][i-1]][i-1];
}
}
}
return;
}
int lca(int a,int b)
{
if(depth[a]<depth[b])swap(a,b);
for(int i=19;i>=0;i--)
if(depth[fa[a][i]]>=depth[b])a=fa[a][i];
if(a==b)return a;
for(int i=19;i>=0;i--)
if(fa[a][i]!=fa[b][i])
a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
int id[N],nowid;
void dfs(int u,int fa)
{
sz[u]=1;
id[u]=++nowid;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa)continue;
dfs(j,u);
sz[u]+=sz[j];
}
return ;
}
void solve()
{
memset(h,-1,sizeof(h));
cin>>n>>m;
_rep(i,2,n)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
bfs(1);
dfs(1,0);
while(m--)
{
cin>>n;
bool bl=true;
int pre=0;
vector<int>v,s;
_rep(i,1,n)cin>>son[i];
_rep(i,1,n)
{
if(pre)
{
int nowsiz=query(id[son[i]]+sz[son[i]]-1)-query(id[son[i]]-1);
if(nowsiz)
{
bl=false;
break;
}
if(pre!=fa[son[i]][0])
{
int lc=lca(pre,son[i]);
bool pan=true;
while(s.size())
{
int pre=s.back();
int presiz=query(id[pre]+sz[pre]-1)-query(id[pre]-1);
s.pp;
if(presiz!=sz[pre])
{
pan=false;
break;
}
}
if(!pan||!fa[son[i]][0]||fa[son[i]][0]!=lc||nowsiz!=0)
{
bl=false;
break;
}
}
}
s.pb(son[i]);
v.pb(id[son[i]]);
addtree(id[son[i]],1);
pre=son[i];
}
for(auto i:v)addtree(i,-1);
if(bl)cout<<"Yes\n";
else cout<<"No\n";
}
return ;
}
signed main()
{
IOS;
int T=1;
// cin>>T;
while(T--)
solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 7ms
memory: 36448kb
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 No
result:
wrong answer 7th words differ - expected: 'Yes', found: 'No'