QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#469074#8720. BFS 序 0JEdwardTL 0ms23300kbC++172.8kb2024-07-09 13:10:402024-07-09 13:10:42

Judging History

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

  • [2024-07-09 13:10:42]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:23300kb
  • [2024-07-09 13:10:40]
  • 提交

answer

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define int long long
#define endl '\n'
#define lowbit(x) (x)&(-x)
#define pii pair<int,int>
#define all(s) s.begin(), s.end()
#define ls(x) (x<<1)
#define rs(x) (x<<1|1) 
#define here system("pause")
using namespace std;

const int N = 3e5+5;
const int mod = 1e9+7;
const int INF = 1e15+7;
const double eps = 1e-6;
inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}
inline int inv(int a, int p){ return pow(a,p-2,p)%p;}

int n, q;
vector<int> g[N], pd[N];
int f[N][20], dep[N], ask[N<<1], indeg[N];
bool flag;

inline void dfs(int u, int fa){
	f[u][0] = fa;
	dep[u] = dep[fa] + 1;
	for(int i=1;i<20 && f[u][i-1];i++){
		f[u][i] = f[f[u][i-1]][i-1];
	}
	for(auto v:g[u]){
		if(v==fa) continue;
		dfs(v, u);
	}
}

inline int getlca(int u, int v){
	if(dep[u]<dep[v]) swap(u, v);
	for(int i=19;i>=0;i--){
		if(dep[f[u][i]]>=dep[v]) u = f[u][i];
	}
	
	if(u==v) return u;
	for(int i=19;i>=0;i--){
		if(f[u][i]!=f[v][i]) u = f[u][i], v = f[v][i];
	}
	return f[v][0];
}

inline void sol(){
	cin >> n;
	for(int i=2;i<=n;i++){
		cin >> f[i][0];
		g[f[i][0]].push_back(i);
//		g[i].push_back(f[i][0]);
	}
	
//	dfs(1, 0);
	for(int i=1;i<=n;i++)
		dep[i]=dep[f[i][0]]+1;
	for(int i=1;i<19;i++)
		for(int j=1;j<=n;j++)
			f[i][j]=f[i-1][f[i-1][j]];
	cin >> q;
	while(q--){
		int num;
		cin >> num;
		flag = 1;
		vector<int> pot;
		for(int i=1;i<=num;i++){
			cin >> ask[i];
			if(i!=1 && dep[ask[i]] < dep[ask[i-1]]) flag = 0;
		}
		
		if(!flag){
			cout << "No\n";
			continue;
		}
		if(num==1){
			cout << "Yes\n";
			continue;
		}
		
		set<int> st;
		for(int i=2;i<=num;i++){
			if(dep[ask[i-1]]==dep[ask[i]]){
				st.insert(ask[i]), st.insert(ask[i-1]);
				pd[ask[i]].clear(), pd[ask[i-1]].clear();
				indeg[ask[i]] = indeg[ask[i-1]] = 0;
			}
		}
		
		for(int i=2;i<=num;i++){
			if(dep[ask[i-1]]==dep[ask[i]]){
				int a = ask[i-1], b = ask[i];
				//cout << getlca(a, b) << " <- " << a << ", " << b << '\t';
				for(int j=19;j>=0;j--){
					if(f[j][a] != f[j][b]) a = f[j][a], b = f[j][b];
				}
				//cout << a << ", " << b << endl;
				
				pd[a].push_back(b);
				++indeg[b];
				
				queue<int> q;
				for(int k:st){
					if(!indeg[k]) q.push(k);
				}
				
				while(q.size()){
					int now = q.front();
					q.pop();
					for(int k:pd[now]){
						--indeg[k];
						if(!indeg[k]) q.push(k);
					}
				}
				
				for(int k:st){
					if(indeg[k]) flag = 0;
					//cout << " " << k << ": " << indeg[k] << endl;
				}
			}
			
		}
		if(!flag) cout << "No\n";
		else cout << "Yes\n";
	}
}

signed main(){
	IOS;
	int tc = 1;
	while(tc--){
		sol();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 23300kb

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
Time Limit Exceeded

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:


result: