QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420377#8720. BFS 序 0Scintilla#WA 101ms138400kbC++203.6kb2024-05-24 16:55:162024-05-24 16:55:22

Judging History

你现在查看的是最新测评结果

  • [2024-05-24 16:55:22]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:138400kb
  • [2024-05-24 16:55:16]
  • 提交

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]