QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#624#414920#8720. BFS 序 0ucup-team052bulijiojiodibuliduoSuccess!2024-05-21 10:04:062024-05-21 10:04:07

Details

Extra Test:

Wrong Answer
time: 197ms
memory: 63348kb

input:

300000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

Yes

result:

wrong answer expected NO, found YES [1st token]

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414920#8720. BFS 序 0bulijiojiodibuliduo#WA 253ms47656kbC++171.8kb2024-05-20 02:23:192024-10-14 17:58:22

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

#define LOGN 18
const int N=301000;
int m,a[N],dep[N],p[N][22],deg[N];
int n,_;
VI e[N];
PII lca(int u,int v) {
	if (dep[u]>dep[v]) swap(u,v);
	per(i,0,LOGN) if (dep[p[v][i]]>=dep[u]) v=p[v][i];
	per(i,0,LOGN) if (p[v][i]!=p[u][i]) u=p[u][i],v=p[v][i];
	return mp(u,v);
}
bool solve() {
	scanf("%d",&m);
	rep(i,0,m) scanf("%d",&a[i]);
	rep(i,1,m) if (dep[a[i]]<dep[a[i-1]]) return false;
	set<int> st;
	bool val=1;
	rep(i,1,m) if (dep[a[i]]==dep[a[i-1]]) {
		if (a[i]==a[i-1]) { val=0; continue; }
		auto [u,v]=lca(a[i-1],a[i]);
		e[u].pb(v);
		st.insert(u);
		st.insert(v);
		deg[v]++;
	}
	queue<int> q;
	for (auto u:st) if (deg[u]==0) {
		q.push(u);
	}
	int cc=0;
	while (!q.empty()) {
		++cc;
		int u=q.front(); q.pop();
		for (auto v:e[u]) {
			--deg[v];
			if (deg[v]==0) q.push(v);
		}
	}
	for (auto u:st) {
		e[u].clear(); deg[u]=0;
	}
	return cc==SZ(st)&&val;
}

int main() {
	scanf("%d",&n);
	for (int i=2;i<=n;i++) {
		scanf("%d",&p[i][0]);
		dep[i]=dep[p[i][0]]+1;
	}
	rep(j,1,LOGN) rep(i,1,n+1) p[i][j]=p[p[i][j-1]][j-1];
	for (scanf("%d",&_);_;_--) {
		puts(solve()?"Yes":"No");
	}
}