글 읽기 - 어....시간초과..?

QuqqU 4년 전 0

시간초과가 뜹니다....

트라이는 제대로 구현한 것 같은데, 도대체 어디서 시간이 터지는지 모르겠습니다.

마음이 울적하고....잠이 안옵니다....

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
using ii = pair<int,int>;
using ll = long long int;

const int num = 15;

struct trie {
    trie* go[num];
    bool output, goexist;
    
    trie() {
        fill(go, go + num, nullptr);
        output = goexist = false;
    }
    
    ~trie() {
        for(trie* t : go) if(t) delete t;
    }
    
    bool insert(const string& s, int i) {        
        int size = s.size();
        if(size == i) {
            output = true;   
            return !goexist;
        }
        
        int next = s[i] - '0';
        if(!go[next]) go[next] = new trie;     
        goexist = true;
   
        return !output && go[next]->insert(s, i + 1);
    }
};



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        trie* t = new trie;
        bool ch = true;
        while(n--){
            string s; cin >> s;
            if(t->insert(s, 0)) continue;
            ch = false; break;
        }
        cout << (ch ? "YES" : "NO") << "\n";
        delete t;
    }

    return 0;
}

djm03178 4년 전 3

전화번호를 목록에 넣는 도중 일관성이 없는 걸 발견했다고 곧바로 break해버리면 그 케이스의 나머지 부분을 다 입력받지 않은 채로 다음 케이스로 넘어가게 됩니다.

QuqqU 4년 전 0

아...! 제가 너무 바보였네요 ㅠㅠ

감사합니다

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

문제

문제

출처

ICPC

어....시간초과..?

QuqqU 4년 전 0

djm03178 4년 전 3

QuqqU 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말