QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692115 | #8551. DFS Order 5 | szy10010 | WA | 0ms | 30048kb | C++23 | 3.2kb | 2024-10-31 13:50:46 | 2024-10-31 13:50:51 |
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],cnt[N],son[N];
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 la(int a,int dep)
//{
// for(int i=19;i>=0;i--)
// if(fa[a][i]<=dep)
// a=fa[a][i];
// return a;
//}
int la(int v, int d) {
for (int k = 20; k >= 0; --k) {
if (d >= (1 << k)) {
v = fa[v][k];
d -= (1 << k);
}
}
return v;
}
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];
}
void dfs(int u,int fa)
{
sz[u]=1;
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;
_rep(i,1,n)
cin>>son[i],cnt[son[i]]=1;
_rep(i,1,n)
{
if(pre)
{
if(pre==fa[son[i]][0])
{
v.pb(son[i]);
pre=son[i];
continue;
}
else
{
bool pan=true;
int lc=lca(pre,son[i]);
while(v.size())
{
if(depth[v.back()]<depth[son[i]])break;
cnt[fa[v.back()][0]]+=cnt[v.back()];
if(cnt[v.back()]!=sz[v.back()])
{
// cout<<v.back()<<" "<<cnt[v.back()]<<" "<<sz[v.back()]<<'\n';
pan=false;
break;
}
v.pp;
}
if(!pan||!fa[son[i]]||fa[son[i]][0]!=lc||cnt[son[i]]!=sz[son[i]])
{
// cout<<son[i]<<" "<<cnt[lc_1]<<" "<<sz[lc_1]<<endl;
bl=false;
break;
}
v.pb(son[i]);
}
}
pre=son[i];
}
if(bl)cout<<"Yes\n";
else cout<<"No\n";
}
return ;
}
signed main()
{
IOS;
int T=1;
// cin>>T;
while(T--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 30048kb
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 No No No Yes No
result:
wrong answer 3rd words differ - expected: 'Yes', found: 'No'