这是dev的bug吗
查看原帖
这是dev的bug吗
1276544
luoguerepp楼主2024/3/23 13:34

为什么用dev跑第一个样例时,最后的ok数组会自己重置为false???

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 3e5 + 10,M = 30;
#define endl '\n'

int n;
string str[N];
int son[N][M],idx;
int cnt[N];
bool edge[M][M];
int in[M];
bool ok[N];

bool topocal(){
    queue<int> q;
    for(int i = 0; i < 26; ++i)
        if(!in[i])  q.push(i);
    
    while(q.size()){
        auto t = q.front();
        q.pop();
        
        for(int i = 0; i < 26; ++i)
            if(edge[t][i]){
                --in[i];
                if(!in[i])  q.push(i);
            }
        
    }
    
    for(int i = 0; i < 26; ++i)
        if(in[i])   return false;
    return true;
}
bool query(string str){
    memset(edge,0,sizeof edge);
    memset(in,0,sizeof edge);
    
    int p = 0;
    for(int i = 0; i < str.size(); ++i){
        int u = str[i] - 'a';
        if(cnt[p])  return false;
        
        for(int j = 0; j < 26; ++j){
            if(u == j || edge[u][j] || !son[p][j])  continue;
            edge[u][j] = true;
            in[j]++;
        }
        
        p = son[p][u];
    }
    
    return topocal();
}
void add(string str){
    int p = 0;
    for(int i = 0; i < str.size(); ++i){
        int u = str[i] - 'a';
        if(!son[p][u])  son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; ++i){
    	cin >> str[i];
        add(str[i]);
    }
    
    int ans = 0;
    for(int i = 0; i < n; ++i){
    	if(query(str[i])){
        	ans++;
        	ok[i] = true;
 		}
	}
					
    cout << ans << endl;
    for(int i = 0; i < n; ++i)
    	if(ok[i])	cout << str[i] << endl;
        
    return 0;
}
2024/3/23 13:34
加载中...