QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#602897 | #8720. BFS 序 0 | frs# | TL | 4ms | 41992kb | C++14 | 3.7kb | 2024-10-01 13:25:07 | 2024-10-01 13:25:08 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N = 5e5 + 5;
int n, qr, m, cnt[N], a[N], du[N], pos[N], p, fa[N];
bool f[N], vis[N], instack[N];
vector<int> ve[N];
vector<int> nve[N];
struct qnode{
int id, d;
qnode(int id1 = 0, int d1 = 0){
id = id1;
d = d1;
}
}tp;
queue<qnode> q;
struct node{
int fr, bk;
node(int fr1 = 0, int bk1 = 0){
fr = fr1;
bk = bk1;
}
}eg[N];
int egp, sd;
bool dfs(int x){
if(vis[x]) return 1;
instack[x] = 1;
int sz = nve[x].size();
for(int i = 0; i < sz; i++){
if(instack[nve[x][i]]){
instack[x] = 0;
return 0;
}
if(!dfs(nve[x][i])){
instack[x] = 0;
return 0;
}
}
vis[x] = 1;
instack[x] = 0;
return 1;
}
int main(){
scanf("%d", &n);
int u;
for(int i = 2; i <= n; i++){
scanf("%d", &u);
ve[u].push_back(i);
fa[i] = u;
}
q.push(qnode(1, 1));
while(!q.empty()){
tp = q.front();
q.pop();
cnt[tp.id] = tp.d;
int sz = ve[tp.id].size();
for(int i = 0; i < sz; i++){
q.push(qnode(ve[tp.id][i], tp.d + 1));
}
}
scanf("%d", &qr);
while(qr--){
scanf("%d", &m);
bool flag = 1;
for(int i = 1; i <= m; i++){
scanf("%d", &a[i]);
f[a[i]] = 0;
if(a[i] < 1 || a[i] > n){
flag = 0;
}
}
f[a[1]] = 1;
for(int i = 2; i <= m; i++){
if(flag == 0) break;
if(cnt[a[i]] < cnt[a[i - 1]]){
flag = 0;
break;
}
if(f[a[i]]){
flag = 0;
break;
}
f[a[i]] = 1;
}
if(!flag){
printf("No\n");
continue;
}
p = 1;
pos[1] = 1;
for(int i = 2; i <= m; i++){
if(cnt[a[i]] != cnt[a[i - 1]]) pos[++p] = i;
}
egp = 0, sd = cnt[pos[p]];
for(int j = pos[p]; j < m; j++){
eg[++egp] = node(a[j], a[j + 1]);
}
for(int i = p - 1; i >= 1; i--){
while(sd > cnt[pos[i]]){
int negp = egp;
egp = 0;
for(int j = 1; j <= negp; j++){
if(fa[eg[j].fr] == fa[eg[j].bk]) continue;
eg[++egp] = node(fa[eg[j].fr], fa[eg[j].bk]);
}
sd--;
}
for(int j = pos[i]; j < pos[i + 1] - 1; j++){
eg[++egp] = node(a[j], a[j + 1]);
}
for(int j = 1; j <= egp; j++){
nve[eg[j].fr].clear();
nve[eg[j].bk].clear();
du[eg[j].fr] = 0;
du[eg[j].bk] = 0;
vis[eg[j].fr] = 0;
vis[eg[j].bk] = 0;
}
for(int j = 1; j <= egp; j++){
nve[eg[j].fr].push_back(eg[j].bk);
du[eg[j].bk]++;
}
bool youruduweiling = 0;
for(int j = 1; j <= egp; j++){
if(du[eg[j].fr] == 0){
youruduweiling = 1;
if(!dfs(eg[j].fr)){
flag = 0;
break;
}
}
}
if(!youruduweiling) flag = 0;
if(!flag) break;
}
if(!flag) printf("No\n");
else printf("Yes\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 41992kb
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...