QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693933#8551. DFS Order 5szy10010WA 7ms36448kbC++233.2kb2024-10-31 16:59:062024-10-31 16:59:14

Judging History

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

  • [2024-10-31 16:59:14]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:36448kb
  • [2024-10-31 16:59:06]
  • 提交

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'