백준5446 용량 부족

작성일 | In

문제 링크

  • http://icpc.me/5446

문제 출처

  • BAPC 2010 예선 E번

사용 알고리즘

  • 트라이

풀이

트라이를 만들고, 각 정점에서 (지워야 하는 문자열의 개수 = a, 지우면 안 되는 문자열의 개수 = b)를 관리합시다.
어떤 정점에서 관리하고 있는 값이 b = 0이고 a ≠ 0이면 경우, 그 정점을 지워주면 됩니다.

즉, 트라이를 구축한 뒤 DFS를 돌면서 a ≠ 0이고 b = 0인 정점을 만나면 정답을 1 증가시긴 뒤 밑으로 더 내려가지 않으면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

struct Node{
    map<char, int> mp;
    int chk[2], ed[2];
    void clear(){ mp.clear(); chk[0] = chk[1] = ed[0] = ed[1] = 0; }
} nd[40404];

int n, m, pv, ans;

void insert(int node, const char *s, int id){
    nd[node].chk[id] = 1;
    if(*s == 0){ nd[node].ed[id] = 1; return; }
    if(!nd[node].mp.count(*s)) nd[node].mp[*s] = ++pv;
    insert(nd[node].mp[*s], s+1, id);
}
void dfs(int node){
    if(!nd[node].chk[1]){ ans++; return; }
    if(nd[node].ed[0]){ ans++; }
    for(auto i : nd[node].mp) dfs(i.y);
}
void clear(int node){
    for(auto i : nd[node].mp) clear(i.y);
    nd[node].clear();
}

void solve(){
    pv = 1; ans = 0;
    cin >> n;
    for(int i=1; i<=n; i++){
        string s; cin >> s; insert(1, s.c_str(), 0);
    }
    cin >> m;
    for(int i=1; i<=m; i++){
        string s; cin >> s; insert(1, s.c_str(), 1);
    }
    dfs(1);
    cout << ans << "\n";
    clear(1);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t; while(t--) solve();
}