QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446989#8720. BFS 序 0275307894a#WA 156ms136288kbC++142.9kb2024-06-17 19:42:132024-06-17 19:42:15

Judging History

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

  • [2024-06-17 19:42:15]
  • 评测
  • 测评结果:WA
  • 用时:156ms
  • 内存:136288kb
  • [2024-06-17 19:42:13]
  • 提交

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';
}

Details

Tip: Click on the bar to expand more detailed information

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]