QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#469086 | #8720. BFS 序 0 | JEdward | TL | 2ms | 13520kb | C++17 | 2.5kb | 2024-07-09 13:26:28 | 2024-07-09 13:26:28 |
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];
int f[N][20], dep[N], ask[N<<1];
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];
}
vector<vector<int>> pd;
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);
cin >> q;
while(q--){
int num;
cin >> num;
flag = 1;
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;
}
pd.resize(n+1, vector<int>());
map<int, pii> deg; // pii -> in & out
for(int i=2;i<=num;i++){
if(dep[ask[i-1]]<dep[ask[i]]) continue;
else if(dep[ask[i-1]]==dep[ask[i]]){
int a = ask[i-1], b = ask[i];
for(int j=19;j>=0;j--){
if(f[j][a] != f[j][b]) a = f[j][a], b = f[j][b];
}
pd[a].push_back(b);
deg[a].second++;
deg[b].first++;
}
}
queue<int> q;
unordered_map<int,int> app;
bool haveS = 0;
for(auto k:deg){
if(k.second.first == 0 && k.second.second != 0){
q.push(k.first);
haveS = 1;
}
}
while(q.size()){
int now = q.front();
q.pop();
for(int k:pd[now]){
if(app.count(k)) flag = 0;
app[k] = 1;
q.push(k);
}
}
if(deg.size() && !haveS) flag = 0;
if(!flag) cout << "No\n";
else cout << "Yes\n";
}
}
signed main(){
IOS;
int tc = 1;
while(tc--){
sol();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 13520kb
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...