QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417931 | #8720. BFS 序 0 | OOBMABTRAMS# | WA | 319ms | 252176kb | C++23 | 2.1kb | 2024-05-23 03:13:50 | 2024-05-23 03:13:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=300013;
vector<int>mp[N];
int dfn[N],dep[N],mnd[19][N],tot;
int s[N],t;
void dfs(int x,int fa){
dep[x]=dep[fa]+1,mnd[0][dfn[x]=++tot]=fa;
for(auto i:mp[x])if(i^fa)dfs(i,x);
}
int get(int x,int y){return dep[x]<dep[y]?x:y;}
int lca(int x,int y){
if(x==y)return x;
x=dfn[x],y=dfn[y];
if(x>y)swap(x,y);
int i=__lg(y-x++);
return get(mnd[i][x],mnd[i][y-(1<<i)+1]);
}
void get_lca(int n){
tot=0,dfs(1,0);
for(int i=1;i<=18;i++)for(int j=1;j+(1<<i)-1<=n;j++)
mnd[i][j]=get(mnd[i-1][j],mnd[i-1][j+(1<<(i-1))]);
}
int id[N],tp[N],occ[N];
queue<int>q[N];
void wk(){
int x,sz;
cin>>x;
vector<int>v(x),v1;
for(auto&p:v)cin>>p,id[p]=1;
for(int i=0;i+1<x;i++){
if(dep[v[i]]>dep[v[i+1]]){
cout<<"No\n";
return;
}
}
v1=v;
sort(v.begin(),v.end(),[&](int x,int y){return dfn[x]<dfn[y];});
for(int i=1;i<x;i++)v.push_back(lca(v[i],v[i-1]));
sort(v.begin(),v.end(),[&](int x,int y){return dfn[x]<dfn[y];});
v.resize(unique(v.begin(),v.end())-v.begin());
sz=v.size();
s[t=1]=v[0];
for(int i=1;i<sz;i++){
while(t){
if(lca(s[t],v[i])==s[t]){
if(id[s[t]])tp[v[i]]=s[t];else tp[v[i]]=tp[s[t]];break;
}
t--;
}
s[++t]=v[i];
}
int flg=1;
for(int i=x-1;~i;i--){
int o=v1[i];
if(occ[o]){
if(q[dep[o]].empty()||q[dep[o]].front()!=o)flg=0;
else q[dep[o]].pop();
}
if(tp[o])if(q[dep[tp[o]]].empty()||q[dep[tp[o]]].back()!=tp[o])q[dep[tp[o]]].push(tp[o]),occ[tp[o]]=1;
}
for(int i=x-1;~i;i--){
occ[v1[i]]=0;
while(!q[dep[v1[i]]].empty())flg=0,q[dep[v1[i]]].pop();
}
if(flg)cout<<"Yes\n";
else cout<<"No\n";
cout<<endl;
}
int main()
{
int n;cin>>n;
for(int i=2,x;i<=n;i++)cin>>x, mp[x].push_back(i), mp[i].push_back(x);
get_lca(n);
//dfs(1,0);
int q;
cin>>q;
for(int i=1;i<=q;i++) wk();
}
详细
Test #1:
score: 100
Accepted
time: 47ms
memory: 215908kb
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: -100
Wrong Answer
time: 319ms
memory: 252176kb
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 Yes No No Yes Yes Yes Yes Yes Yes No No Yes No Yes No Yes No Yes Yes Yes Yes No Yes Yes No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes Yes Yes Yes No No No Yes Yes Yes No Yes No Yes Yes No No No Yes Yes No Yes Yes Yes Yes Yes No No...
result:
wrong answer expected NO, found YES [1st token]