글 읽기 - 시간 초과 질문입니다..

smy4024169 2년 전 0

색은 정방향, 이름은 역방향으로 각각 트라이에 저장하였고, 팀명을 정방향과 역방향 한 번씩 탐색해서 O(N)이 되도록 만들었습니다.

그런데 2%에서 시간초과가 뜨는 것을 보면 뭔가 예외를 처리하지 못한 것 같은데, 어떤 문제인지 감이 잡히지 않아 질문드립니다..

#include <bits/stdc++.h>
#define mod 1000000007
#define FIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define priority_queue_(x) priority_queue<x, vector<x>, greater<x>>
#define priority_queue_pair priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
typedef long long ll;
using namespace std;
int ny[4] = { 1, 0, -1, 0 };
int nx[4] = { 0, 1, 0, -1 };

//trie[노드 개수][알파벳 idx]
int Next[5000000][26][2];
bool Finish[5000000][2];
int p;
int check[2001];

void insert(string str, int cnt) {
    int node = 0;
    for (int i = 0; i < str.size(); i++) {
        int curr;
        if (str[i] >= 'a') curr = str[i] - 'a';
        else curr = str[i] - 'A';

        if (not Next[node][curr][cnt]) Next[node][curr][cnt] = ++p;
        node = Next[node][curr][cnt];
    }
    
    Finish[node][cnt] = true;
}
int find(string str, int cnt) {
    int node = 0;
    for (int i = 0; i < str.size(); i++) {

        if (Finish[node][cnt]) {
            if (cnt) check[str.size() - i]++;
            else check[i]++;
        }

        int curr;
        if (str[i] >= 'a') curr = str[i] - 'a';
        else curr = str[i] - 'A';

        if (not Next[node][curr][cnt]) return 0;
        node = Next[node][curr][cnt];

    }  
    return node;
}

int main(void)
{
    FIO;
    int N, M; cin >> N >> M;
    string str;
    for (int i = 0; i < N; i++) {
        cin >> str;
        insert(str, 0);
    }
    p = 0;
    for (int i = 0; i < M; i++) {
        cin >> str;
        reverse(str.begin(), str.end());
        insert(str, 1);
    }

    int Q; cin >> Q;
    for (int i = 0; i < Q; i++) {
        cin >> str;
        memset(check, 0, sizeof(check));

        find(str, 0);
        reverse(str.begin(), str.end());
        find(str, 1);

        bool flag = false;
        for (int j = 1; j < str.size(); j++) if (check[j] >= 2) flag = true;
        if (flag) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

daniel604 4달 전 0

저도 같은 문제를 겪었습니다만 두 trie 배열을 3차원으로 두지 말고 2차원 배열 둘로 쪼개면 시간 초과를 해결할 수 있었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과 질문입니다..

smy4024169 2년 전 0

daniel604 4달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말