QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#446989 | #8720. BFS 序 0 | 275307894a# | WA | 156ms | 136288kb | C++14 | 2.9kb | 2024-06-17 19:42:13 | 2024-06-17 19:42:15 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e6+5,M=N*4+5,K=1000+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
int n,k,B[N],q;vector<int> S[N];
int fa[N],d[N],siz[N],son[N],tp[N];
void dfs1(int x,int La){
fa[x]=La;siz[x]=1;d[x]=d[La]+1;
for(int i:S[x]) if(i^La) dfs1(i,x),siz[x]+=siz[i],siz[i]>siz[son[x]]&&(son[x]=i);
}
void dfs2(int x,int La){
tp[x]=La;if(son[x]) dfs2(son[x],La);
for(int i:S[x]) if(i^fa[x]&&i^son[x]) dfs2(i,i);
}
int LCA(int x,int y){
while(tp[x]^tp[y]){
if(d[tp[x]]<d[tp[y]]) swap(x,y);
x=fa[tp[x]];
}
return d[x]<d[y]?x:y;
}
int jump(int x,int y){
while(d[fa[tp[x]]]>d[y]) x=fa[tp[x]];
if(tp[x]==tp[y]) return son[y];
return tp[x];
}
set<pii> f[N];
queue<int> Q;
vector<int> G[N];int in[N];
int check(int x){
static int st[N],sh;
sh=0;
for(auto i:f[x]) G[i.fi].push_back(i.se),in[i.se]++,st[++sh]=i.fi,st[++sh]=i.se;
sort(st+1,st+sh+1);sh=unique(st+1,st+sh+1)-st-1;
for(int i=1;i<=sh;i++) if(!in[st[i]]) Q.push(st[i]);
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i:G[x]) if(!--in[i]) Q.push(i);
}
int flag=0;
for(int i=1;i<=sh;i++) G[st[i]].clear(),flag|=in[i],in[i]=0;
f[x].clear();
return flag;
}
void Solve(){
int i,j;scanf("%d",&n);
for(i=2;i<=n;i++){
int x,y;scanf("%d",&x);
S[x].push_back(i);S[i].push_back(x);
}
dfs1(1,0);dfs2(1,1);
scanf("%d",&q);
static int ap[N];
Me(ap,0);
while(q--){
scanf("%d",&k);
for(i=1;i<=k;i++) scanf("%d",&B[i]);
int flag=0;
for(i=1;i<=k;i++){
if(ap[B[i]]) flag=1;
ap[B[i]]=1;
}
for(i=1;i<=k;i++) ap[B[i]]=0;
for(i=1;i<k;i++) if(d[B[i]]>d[B[i+1]]) flag=1;
static int st[N],sh;
sh=0;
for(i=1;i<k;i++) if(d[B[i]]==d[B[i+1]]){
int v=LCA(B[i],B[i+1]);
st[++sh]=v;
f[v].emplace(jump(B[i],v),jump(B[i+1],v));
}
sort(st+1,st+sh+1);sh=unique(st+1,st+sh+1)-st-1;
for(i=1;i<=sh;i++) if(check(st[i])) flag=1;
puts(flag?"No":"Yes");
}
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 12ms
memory: 112464kb
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: 156ms
memory: 136288kb
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 No No No Yes No No No Yes No No Yes No No Yes Yes Yes No No No Yes...
result:
wrong answer expected YES, found NO [71st token]