QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602897#8720. BFS 序 0frs#TL 4ms41992kbC++143.7kb2024-10-01 13:25:072024-10-01 13:25:08

Judging History

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

  • [2024-10-01 13:25:08]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:41992kb
  • [2024-10-01 13:25:07]
  • 提交

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

详细

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...

output:


result: