oj.uz

Submission #824132

# Submission time Handle Problem Language Result Execution time Memory
824132 2023-08-13T15:09:06 Z hafo Type Printer (IOI08_printer) C++14
100 / 100
 145 ms 106472 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n;
vector<char> res;
string st;

struct node {
    node* child[26];
    int cnt, deep, mx, pos;

    node () {
        for(int i = 0; i < 26; i++) child[i] = NULL;
        cnt = deep = mx = 0;
    }
};

node* root = new node();

struct trie {
    void add(string &st) {
        auto p = root;
        for(int i = 0; i < Size(st); i++) {
            int nxt = st[i] - 'a';
            if(p -> child[nxt] == NULL) p -> child[nxt] = new node();
            p = p -> child[nxt];
        }
        p -> cnt++;
    }

    void dfs2(node* u) {
        u -> mx = u -> deep;
        for(int i = 0; i < 26; i++) {
            if(u -> child[i] == NULL) continue;
            auto v = u -> child[i];
            v -> deep = u -> deep + 1;
            dfs2(v);
            if(maxi(u -> mx, v -> mx)) u -> pos = i;
        }
    }

    void dfs(node* u, bool ok) {
        if(u -> cnt == 1) res.pb('P');
        for(int i = 0; i < 26; i++) {
            if(u -> child[i] == NULL || (ok && u -> pos == i)) continue;
            res.pb(char(i + 'a'));
            dfs(u -> child[i], 0);
            res.pb('-');
        }

        if(ok) {
            for(int i = 0; i < 26; i++) {
                if(u -> child[i] == NULL) continue;
                if(i == u -> pos) {
                    res.pb(char(i + 'a'));
                    dfs(u -> child[i], 1);
                }
            }
        }
    }

} trie;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n;
    for(int i = 0; i < n; i++) {
        cin>>st;
        trie.add(st);
    }

    trie.dfs2(root);
    trie.dfs(root, 1);
    cout<<Size(res)<<"\n";
    for(auto i:res) cout<<i<<"\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 3 ms 2388 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6356 KB Output is correct
2 Correct 17 ms 13396 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15776 KB Output is correct
2 Correct 7 ms 3540 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 39232 KB Output is correct
2 Correct 121 ms 89444 KB Output is correct
3 Correct 65 ms 46156 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 30552 KB Output is correct
2 Correct 145 ms 106472 KB Output is correct
3 Correct 92 ms 52324 KB Output is correct
4 Correct 116 ms 100420 KB Output is correct