QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#416639 | #8720. BFS 序 0 | Afterlife# | WA | 112ms | 740392kb | C++17 | 3.6kb | 2024-05-22 01:18:06 | 2024-05-22 01:18:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e3+7;
int n,st[N],ed[N],dep[N],dc;
vector<int> g[N];
int anc[N][21];
void dfs(int x,int f)
{
st[x]=++dc;
anc[x][0]=f;
for(int j=1;j<=20;j++)
anc[x][j]=anc[anc[x][j-1]][j-1];
for(auto v:g[x])
{
if(v==f)
continue;
dep[v]=dep[x]+1;
dfs(v,x);
}
ed[x]=dc;
}
int fup(int a,int b)
{
for(int i=20;i>=0;i--)
if(dep[a]-(1<<i)>dep[b])
a=anc[a][i];
return a;
}
int lca(int x,int y)
{
if(dep[x]<dep[y])
swap(x,y);
for(int i=20;i>=0;i--)
if(dep[x]-(1<<i)>=dep[y])
x=anc[x][i];
if(x==y)
return x;
for(int i=20;i>=0;i--)
if(anc[x][i]!=anc[y][i])
x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
namespace SOLVE {
int m, i, a[N], q[N], t, tot;
int pos[N];
void dfs(int x)
{
for(auto v:g[x])
dfs(v),pos[x]=min(pos[x],pos[v]);
}
bool vip[N], vis[N];
bool cmp(int x, int y) { return st[x] < st[y]; }
vector<int> g[N];
queue<int> Q[N];
void solve(vector<int> v,vector<int> seq) {
for(int i=0;i+1<seq.size();i++)
{
int x=seq[i],y=seq[i+1];
if(dep[x]!=dep[y])
continue;
int z=lca(x,y);
v.push_back(fup(x,z));
v.push_back(fup(y,z));
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int la=-1;
bool ok=1;
for(auto x:seq)
{
if(dep[x]<la)
ok=0;
la=dep[x];
}
if(!ok)
{
cout<<"No\n";
return;
}
if (!v.size())
return;
vis[1] = vip[1] = a[1] = 1;
m = v.size();
for (tot = ++m, i = 2; i <= m; i++)
a[i] = v.back(), v.pop_back(), vis[a[i]] = vip[a[i]] = 1;
sort(a + 1, a + m + 1, cmp);
int x;
for (i = 1; i < m; i++)
if (!vis[x = lca(a[i], a[i + 1])])
vis[a[++tot] = x] = 1;
vector<int> use;
m = tot, sort(a + 1, a + m + 1, cmp);
for (q[t = 1] = 1, i = 2; i <= m; q[++t] = a[i++]) {
while (st[a[i]] < st[q[t]] || ed[a[i]] > ed[q[t]]) // dfs order
t--;
if (q[t] != a[i])
g[q[t]].push_back(a[i]);
use.push_back(q[t]);
use.push_back(a[i]);
}
for(auto x:use)
pos[x]=1e9;
// solve the problem
for(int i=0;i<seq.size();i++)
pos[seq[i]]=i;
dfs(1);
set<int> s;
Q[0].push(1);
s.insert(0);
auto it=seq.begin();
while(!s.empty())
{
int d=*s.begin();
while(!Q[d].empty())
{
int x=Q[d].front();
Q[d].pop();
if(it!=seq.end()&&x==*it)
it++;
sort(g[x].begin(),g[x].end(),[&](const int &a,const int &b){return pos[a]<pos[b];});
for(auto v:g[x])
{
Q[dep[v]].push(v);
s.insert(dep[v]);
}
}
s.erase(s.begin());
}
ok&=it==seq.end();
if(ok)
cout<<"Yes\n";
else
cout<<"No\n";
for (auto x : use)
vis[x] = vip[x] = 0, g[x].clear();
return;
}
} // namespace SOLVE
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=2;i<=n;i++)
{
int f;
cin>>f;
g[f].push_back(i);
}
dfs(1,0);
int m;
cin>>m;
while(m--)
{
int k;
cin>>k;
vector<int> s;
while(k--)
{
int x;
cin>>x;
s.push_back(x);
}
SOLVE::solve(s,s);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 112ms
memory: 740392kb
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:
No Yes No No No No No No No Yes
result:
wrong answer expected YES, found NO [3rd token]