QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#469077 | #8720. BFS 序 0 | JEdward | TL | 2ms | 22552kb | C++17 | 2.8kb | 2024-07-09 13:12:19 | 2024-07-09 13:12:19 |
Judging History
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(ask[i-1]==ask[i]) flag = 0;
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: 2ms
memory: 22552kb
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...