QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#741191 | #8720. BFS 序 0 | ucup-team4352# | AC ✓ | 352ms | 79424kb | C++23 | 3.0kb | 2024-11-13 13:44:39 | 2024-11-13 13:44:39 |
Judging History
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;
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);
}
if(flag){
cout<<"No\n";
continue;
}
vector<int>r=p;
sort(r.begin(),r.end());
r.resize(unique(r.begin(),r.end())-r.begin());
if(r.size()!=p.size()){
cout<<"No\n";continue;
}
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));
}
}
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;
}
/*
7
1 1 2 2 3 3
1
5 1 3 2 7 5
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
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7736kb
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 Yes No No No No No No Yes
result:
ok 10 token(s): yes count is 3, no count is 7
Test #2:
score: 0
Accepted
time: 346ms
memory: 78380kb
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:
No Yes Yes Yes No No No No No No Yes Yes No Yes No Yes Yes Yes No No No No Yes No No Yes No No No No Yes Yes Yes No No Yes No No No No No No No Yes No Yes No Yes No No No No Yes Yes Yes No No Yes No No No No No Yes Yes No No No No No Yes Yes No Yes No No No Yes No No Yes No No Yes Yes Yes No No No Y...
result:
ok 254 token(s): yes count is 89, no count is 165
Test #3:
score: 0
Accepted
time: 352ms
memory: 79424kb
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 No No Yes No No Yes Yes No Yes No Yes No No No Yes No No No No Yes No No No No No Yes Yes No No No Yes No No No No No Yes Yes Yes No No No No No No No Yes No Yes No No No Yes No No No Yes No No Yes No Yes Yes No No No Yes No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No Yes No No No No No Yes No ...
result:
ok 266 token(s): yes count is 102, no count is 164
Test #4:
score: 0
Accepted
time: 347ms
memory: 79412kb
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:
No No Yes No Yes No No No No No No No No Yes No No No No No No No No Yes No No No No Yes No No No No No No No Yes Yes No No No No No No Yes No No No Yes Yes No No No Yes Yes No Yes No Yes No Yes No Yes No Yes No No Yes No No No No No No No Yes Yes No Yes No No No No No No Yes Yes No Yes Yes No No No...
result:
ok 252 token(s): yes count is 87, no count is 165
Test #5:
score: 0
Accepted
time: 6ms
memory: 7664kb
input:
10 1 1 3 3 1 3 1 3 9 10000 4 3 5 6 9 5 3 1 4 9 6 5 6 4 3 5 7 28 8 3 4 3 1 6 3 5 8 7 2 4 4 4 2 7 5 9 2 4 10 8 4 10 3 4 5 7 3 5 2 9 6 4 7 2 3 9 5 5 9 2 5 6 1 12 3 5 8 8 1 3 5 8 4 5 9 1 29 3 9 9 1 5 8 5 5 6 10 8 8 4 8 4 2 8 10 5 7 3 7 1 8 4 7 5 1 6 7 5 9 8 3 2 1 6 4 4 1 9 5 22 10 9 5 4 5 8 10 3 2 1 10 ...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No Yes No No No No No Yes No No No No No No No Yes No No No No Yes No No No Yes No No Yes No No No No No No No No No No No No No No No Yes No Yes No No No No No No No No No Yes Yes No Yes No No No No No No ...
result:
ok 10000 token(s): yes count is 1058, no count is 8942
Test #6:
score: 0
Accepted
time: 6ms
memory: 7620kb
input:
9 1 2 1 2 2 4 2 6 10000 6 5 1 4 3 7 8 14 6 8 7 9 7 5 1 8 3 6 3 8 5 2 2 6 9 17 7 8 6 5 2 1 5 5 9 3 4 1 5 2 7 2 5 3 8 6 5 5 3 9 1 6 8 8 3 5 8 7 9 4 6 2 4 8 9 6 5 7 4 7 2 9 3 8 1 6 1 4 9 5 6 2 4 7 5 4 3 5 9 5 2 1 3 4 4 5 7 3 3 9 1 8 4 4 2 8 6 26 7 4 7 6 1 7 9 4 5 5 8 9 8 2 4 8 9 6 2 8 6 4 5 5 4 4 45 3 ...
output:
No No Yes No Yes No No No No No No No No No Yes No No No No No No Yes No No No No No No Yes No No No No No No No No Yes Yes No No No Yes No No No No No No No No No No No No Yes No No No No No No No No No No No No No Yes No Yes No No No No No No No No Yes No No No Yes No No Yes No No No No No No No N...
result:
ok 10000 token(s): yes count is 1492, no count is 8508
Test #7:
score: 0
Accepted
time: 2ms
memory: 7656kb
input:
8 1 1 2 4 2 4 6 10000 5 2 6 6 2 1 3 7 3 8 2 8 1 5 7 5 1 2 7 3 2 3 5 3 8 4 3 5 8 2 4 5 3 4 3 2 1 8 6 6 8 4 5 3 1 6 3 1 2 7 4 6 4 8 6 4 3 5 4 7 6 8 5 11 2 1 6 5 2 7 1 3 3 5 4 4 6 1 7 2 7 6 2 7 8 4 1 3 3 4 6 7 3 7 1 6 38 3 4 6 6 3 4 8 1 5 3 1 8 8 6 2 3 6 7 8 8 4 2 3 7 3 3 6 7 7 5 7 5 8 8 5 4 5 7 1 8 5 ...
output:
No No No No Yes No No No No No No No No No No Yes No No Yes No No No No No Yes No Yes No No No Yes Yes No No No No No No Yes No No No No No No No No No No No Yes No No No No No No No No No Yes No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No Yes No No No No No ...
result:
ok 10000 token(s): yes count is 1568, no count is 8432
Test #8:
score: 0
Accepted
time: 5ms
memory: 7732kb
input:
7 1 2 3 1 2 5 10000 5 1 7 3 5 6 5 5 3 2 7 4 4 5 2 6 4 12 3 1 5 5 6 6 3 5 3 5 3 3 11 2 3 2 6 7 3 6 6 3 3 3 2 3 2 6 1 3 4 2 6 7 3 2 7 1 6 5 2 7 3 4 1 27 2 5 6 1 7 1 7 1 4 6 7 1 6 2 1 7 1 3 4 4 7 7 2 6 4 4 3 2 5 6 1 7 3 3 1 4 4 1 7 3 4 3 4 2 1 4 4 1 6 7 4 6 2 7 4 4 5 1 6 4 1 3 5 1 2 3 5 7 5 2 3 7 6 5 1...
output:
No No Yes No No No No No No No Yes Yes No Yes No No No No Yes No No No No Yes No No Yes No No No No No No No No No No No No No No No No No No No No No No No Yes No No Yes No Yes Yes No Yes Yes No No No No No No No No No No Yes No No No No No No No No Yes No Yes No No No No Yes Yes Yes Yes Yes Yes Ye...
result:
ok 10000 token(s): yes count is 2205, no count is 7795
Extra Test:
score: 0
Extra Test Passed