QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#624 | #414920 | #8720. BFS 序 0 | ucup-team052 | bulijiojiodibuliduo | Success! | 2024-05-21 10:04:06 | 2024-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]
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414920 | #8720. BFS 序 0 | bulijiojiodibuliduo# | WA | 253ms | 47656kb | C++17 | 1.8kb | 2024-05-20 02:23:19 | 2024-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");
}
}