oj.uz

답안 #745629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745629 2023-05-20T16:45:03 Z quochuy147 Type Printer (IOI08_printer) C++14
0 / 100
 54 ms 50856 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define file "name" 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

const int mod = 1e9 + 7;
const int N = 1e6 + 5;

int n, check[N], d, m[N];

struct trie
{
    struct node {
        int child[26];
        int cnt, exist;
    } nodes[N];

    int cur;
    trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof nodes[0].child);
        nodes[0].cnt = nodes[0].exist = 0;
    }

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof nodes[cur].child);
        nodes[cur].cnt = nodes[cur].exist = 0;
        return cur;
    }

    void insert(string s, bool check) {
        int id = 0;
        for(auto i : s) {
            int c = i - 'a';
            if(nodes[id].child[c] == -1) nodes[id].child[c] = new_node();
            id = nodes[id].child[c];
            if(check) m[id] = 1;
            nodes[id].cnt++;
        }
        nodes[id].exist++;
    }

    void dfs(int id) {
        if(d == n) exit(0);
        int v_last = 0, i_last;
        for(int i = 0; i < 26; ++i) {
            int v = nodes[id].child[i];
            if(v == -1 || check[v]) continue;
            if(m[v]) {
                v_last = v;
                i_last = i;
                continue;
            }
            cout << char(i + 'a') << '\n';
            for(int j = 1; j <= nodes[v].exist; ++j) {
                cout << "P\n";
                d++;
            }
            check[v] = 1;
            dfs(v);
            cout << "-\n";
        }
        if(v_last) {
            cout << char(i_last + 'a') << '\n';
            for(int j = 1; j <= nodes[v_last].exist; ++j) {
                cout << "P\n";
                d++;
            }
            check[v_last] = 1;
            dfs(v_last);
            cout << "-\n";
        }
    }
};

trie T;
string s[N];
int id_mx;

void inp()
{
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i];
        if(s[i].size() > s[id_mx].size()) id_mx = i; 
    }
    for(int i = 1; i <= n; ++i) {
        if(id_mx == i) T.insert(s[i], 1);
        else T.insert(s[i], 0);
    }
}

void solve()
{
    T.dfs(0);    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen(file".inp" , "r" , stdin);
    // freopen(file".out" , "w" , stdout);
    inp();
    solve();
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 31572 KB Expected integer, but "t" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 31648 KB Expected integer, but "e" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 31652 KB Expected integer, but "h" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 31572 KB Expected integer, but "b" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 31644 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 32468 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 34584 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 39248 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 50856 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 46412 KB Expected integer, but "a" found
2 Halted 0 ms 0 KB -