QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#741104#8720. BFS 序 0ucup-team4352#WA 2ms7672kbC++232.9kb2024-11-13 13:21:452024-11-13 13:21:45

Judging History

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

  • [2024-11-13 13:21:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7672kb
  • [2024-11-13 13:21:45]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define log(x) (31^__builtin_clz(x))
using namespace std;
const int maxn=3e5+5;
vector<int>e[maxn],s[maxn];
int f[maxn],dfn[maxn],dep[maxn];
int st[maxn][20],fa[maxn][20];
int tot;
inline int get(int x,int y){
	return dep[x]<dep[y]?x:y;
}
int lca(int x,int y){
	x=dfn[x];y=dfn[y];
	if(x>y)swap(x,y);
	x++;
	int tmp=log(y-x+1);
	return get(st[x][tmp],st[y-(1<<tmp)+1][tmp]);
}
void dfs(int x){
	dfn[x]=++tot;
	if(x==1)dep[x]=1;
	fa[x][0]=st[dfn[x]][0];
	for(int i=1;i<20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(auto u:e[x]){
		dep[u]=dep[x]+1;
		st[tot+1][0]=x;
		dfs(u);
	}
}
bool cmp(int a,int b){
	return dfn[a]<dfn[b];
}
int flag=0;
int instack[maxn],vis[maxn];
int find(int x,int y){
	for(int i=19;i>=0;i--){
		if(y>>i&1)x=fa[x][i];
	}
	return x;
}
int build(vector<int>t){
	sort(t.begin(),t.end(),cmp);
	t.resize(unique(t.begin(),t.end())-t.begin());

	for(int i=(int)t.size()-1;i;i--){
		t.push_back(lca(t[i],t[i-1]));
	}

	sort(t.begin(),t.end(),cmp);
	t.resize(unique(t.begin(),t.end())-t.begin());

	for(auto u:t)s[u].clear(),vis[u]=instack[u]=0;
	
	vector<int>st;
	for(auto u:t){
		if(st.empty())st.push_back(u);
		else{
			while(st.size()&&lca(st.back(),u)!=st.back())st.pop_back();
			if(st.size()){
				s[st.back()].push_back(u);
			}
		}
	}
	return t[0];
}
void dfs2(int x){
	if(instack[x]){
		flag=1;
		return;
	}
	if(vis[x]||flag)return;
	instack[x]=1;
	vis[x]=1;
	for(auto u:s[x]){
		if(flag)break;
		dfs2(u);
	}
	instack[x]=0;
}
void solve(){
	int n;
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>f[i];
		e[f[i]].push_back(i);
	}
	dfs(1);
	for(int i=n;i>=1;i--){
		for(int j=1;j<20;j++){
			st[i][j]=get(st[i][j-1],st[min(n,i+(1<<j-1))][j-1]);
		}
	}
	int q;
	cin>>q;
	cout<<lca(4,7)<<"\n";
	while(q--){
		int m;
		cin>>m;
		vector<int>p;
		flag=0;
		for(int i=1;i<=m;i++){
			int x;
			cin>>x;
			if(i>1){
				if(dep[x]<dep[p.back()])flag=1;
			}
			p.push_back(x);
		}
		vector<int>p1=p;
		for(int i=1;i<m;i++){
			if(dep[p[i]]==dep[p[i-1]]){
				int l=lca(p[i-1],p[i]);
				int d=dep[p[i]]-dep[l]-1;
				if(l)p1.push_back(find(p[i],d)),p1.push_back(find(p[i-1],d));
			}
		}
		if(flag){
			cout<<"No\n";
			continue;
		}
		int rt=build(p1);
		for(int i=0;i+1<p.size();i++){
			if(dep[p[i]]==dep[p[i+1]]){
				int l=lca(p[i+1],p[i]);
				int d=dep[p[i]]-dep[l]-1;
				// cout<<l<<" "<<d<<"!!!\n";
				s[find(p[i],d)].push_back(find(p[i+1],d));
				// cout<<find(p[i],d)<<" "<<find(p[i+1],d)<<"\n";
			}
		}
		dfs2(rt);
		if(flag){
			cout<<"No\n";
			continue;
		}
		cout<<"Yes\n";
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int t=1;
	// cin>>t;
	while(t--)solve();
	return 0;
}
/*
6
1 1 3 2 4
10
4 3 6 2 5
1 4
3 2 4 5
5 2 5 4 6 3
3 1 4 2
3 5 6 3
5 4 5 2 6 1
4 4 3 2 5
4 4 6 2 3
3 3 2 6
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 7672kb

input:

6
1 1 3 2 4
10
4 3 6 2 5
1 4
3 2 4 5
5 2 5 4 6 3
3 1 4 2
3 5 6 3
5 4 5 2 6 1
4 4 3 2 5
4 4 6 2 3
3 3 2 6

output:

0
No
Yes
Yes
No
No
No
No
No
No
Yes

result:

wrong output format YES or NO expected, but 0 found [1st token]