QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#420377 | #8720. BFS 序 0 | Scintilla# | WA | 101ms | 138400kb | C++20 | 3.6kb | 2024-05-24 16:55:16 | 2024-05-24 16:55:22 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define SZ(x) ((LL)(x.size()))
#define all(x) (x).begin(),(x).end()
using namespace std;
inline LL read(){
LL q=0,w=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){q=q*10+(ch-'0');ch=getchar();}
return q*w;
}
void write(LL x){
if(x<0){putchar('-');x=(-x);}
if(x>9)write(x/10);
putchar('0'+x%10);
}
inline void writeln(LL x){write(x);puts("");}
inline void writecs(LL x){write(x);putchar(' ');}
const long long N = 300000+95 , L = 20+2;
LL n,fa[N];vector<LL>E[N];
LL dep[N],dfn[N],low[N],tim,seq[N];
void dfs(LL x){
dep[x]=dep[fa[x]]+1;dfn[x]=++tim;seq[tim]=x;
for(auto y:E[x])dfs(y);
low[x]=tim;return ;
}
namespace ST{
inline LL merge(LL x,LL y){return ((dep[x]<dep[y])?(x):(y));}
LL lg[N],dp[L][N];
inline void init(){
lg[0]=-1;for(LL i=1;i<=n;i++){lg[i]=lg[i>>1]+1;dp[0][i]=seq[i];}
for(LL k=1;k<=lg[n];k++)
for(LL i=1;i<=n-(1<<k)+1;i++)dp[k][i]=merge(dp[k-1][i],dp[k-1][i+(1<<(k-1))]);
return ;
}
inline LL qry(LL l,LL r){
LL k=lg[r-l+1];
return merge(dp[k][l],dp[k][r-(1<<k)+1]);
}
}
inline LL get_lca(LL x,LL y){
if(x==y)return x;
x=dfn[x];y=dfn[y];if(x>y)swap(x,y);
x++;return fa[ST::qry(x,y)];
}
inline LL dist(LL x,LL y){return (dep[x]+dep[y]-dep[get_lca(x,y)]);}
LL jmp[L][N];
inline LL kth(LL x,LL k){
// cout<<"> x = "<<x<<" k = "<<k<<endl;
for(LL i=20;i>=0;i--)
if((k>>i)&1)x=jmp[i][x];
// cout<<" -> x = "<<x<<endl;
return x;
}
inline LL GET(LL x,LL lca){return kth(x,(dep[x]-dep[lca]-1));}
vector<LL>e[N];bool vis[N];
bool DFS(LL x){
if(vis[x])return false;
vis[x]=1;
for(auto y:e[x])
if(!DFS(y))return false;
return true;
}
/*LL ord[N];vector<LL>e[N];
bool DFS(LL x,LL fr=0,LL FA=0){
if(ord[x]&&fr>ord[x])return false;
if(ord[x])fr=ord[x];
for(auto y:e[x]){
if(y==FA)continue;
if(!DFS(y,fr,x))return false;
}
return true;
}*/
int main(){
n=read();for(LL i=2;i<=n;i++){fa[i]=read();E[fa[i]].push_back(i);}
dfs(1);ST::init();
for(LL i=1;i<=n;i++)jmp[0][i]=fa[i];
for(LL k=1;k<=20;k++)
for(LL i=1;i<=n;i++)jmp[k][i]=jmp[k-1][jmp[k-1][i]];
LL TC=read();
while(TC--){
LL k=read();vector<LL>vc(k);
for(LL i=0;i<k;i++)vc[i]=read();
LL fl=1;
for(LL i=1;i<k;i++)
if(dep[vc[i-1]]>dep[vc[i]]){fl=0;break;}
if(!fl){puts("No");continue;}
vector<LL>vec;
for(LL l=0,r=0;l<k;l=r+1){
r=l;while(r+1<k&&dep[vc[l]]==dep[vc[r+1]])r++;
for(LL i=l+1;i<=r;i++){
LL lca=get_lca(vc[i-1],vc[i]);
LL X=GET(vc[i-1],lca),Y=GET(vc[i],lca);
// cout<<"> X = "<<X<<" Y = "<<Y<<endl;
e[X].push_back(Y);vec.push_back(X);vec.push_back(Y);
}
}
for(auto x:vec)
if(!vis[x]){if(!DFS(x)){fl=0;break;}}
if(!fl)puts("No");
else puts("Yes");
for(auto x:vec){e[x].clear();vis[x]=0;}
/* LL k=read();vector<LL>vc(k);LL s=0;
for(LL i=0;i<k;i++){vc[i]=read();ord[vc[i]]=i+1;}
s=vc[0];
sort(all(vc),[&](LL x,LL y){return dfn[x]<dfn[y];});
for(LL i=SZ(vc)-1;i>0;i--)vc.push_back(get_lca(vc[i-1],vc[i]));
sort(all(vc),[&](LL x,LL y){return dfn[x]<dfn[y];});
vc.erase(unique(all(vc)),vc.end());
vector<LL>st;
auto add_e=[&](LL u,LL v){e[u].push_back(v);e[v].push_back(u);return ;};
for(LL i=0;i<SZ(vc);i++){
while(SZ(st)&&low[st.back()]<dfn[vc[i]])st.pop_back();
if(SZ(st))add_e(st.back(),vc[i]);
st.push_back(vc[i]);
}
LL fl=DFS(s);
if(fl)puts("Yes");
else puts("No");
for(auto x:vc)e[x].clear();*/
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 60972kb
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: 101ms
memory: 138400kb
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 No No No No No No No No Yes Yes No Yes No Yes Yes Yes No No No No No No No Yes No No No No Yes Yes No No No Yes No No No No No No No Yes No Yes No Yes No No No No No Yes Yes No No Yes No No No No No Yes Yes No No No No No No No No Yes No No No Yes No No Yes No No Yes No Yes No No No Yes No No ...
result:
wrong answer expected YES, found NO [2nd token]