oj.uz

답안 #720553

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
720553 2023-04-08T13:12:19 Z nihaddhuseynli Type Printer (IOI08_printer) C++14
100 / 100
 143 ms 108448 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 0
#else
#include "../template/debug.cpp"
#endif
using namespace std;
using ll = int_fast64_t;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define pq priority_queue
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FORE(i,a,b) for(int i = (a); i <= (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define trav(a,x) for(auto& a: x)
#define sz(x) (int)x.size()
 
template<class T> using minpq = pq<T, vector<T>, greater<T>>;
template<class T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
template<class T> bool ckmax(T& a, const T& b){return a<b?a=b,1:0;}
template<int D, typename T>struct vt : public vector<vt<D - 1, T>> { template<typename... Args>
    vt(int n = 0, Args... args) : vector<vt<D - 1, T>>(n, vt<D - 1, T>(args...)) {}};
template<typename T> struct vt<1, T> : public vector<T> {
    vt(int n = 0, const T& val = T()) : vector<T>(n, val) {}};
    
vector<char> ans;

struct trie {
    trie* children[26] = {};
    int last = 69, mxd = -1;
    bool isleaf = false;
};

void trie_add(trie* root, string s) {
    trie* cur = root;
    FOR(i,0,sz(s)){
        int c = s[i] - 'a';
        if (cur->children[c] == NULL)
            cur->children[c] = new trie;
        if(ckmax(cur -> mxd, sz(s) - i - 1)){
            cur -> last = c;
        }
        cur = cur->children[c];
    }
    cur->isleaf = true;
}

void dfs(trie* root){
    if(root -> isleaf) ans.pb('P');
    FOR(i,0,26) if(root -> children[i] != NULL && i != root -> last) {
        ans.pb(char(i + 'a'));
        dfs(root -> children[i]);
    }
    if(root -> last != 69) {
        ans.pb(char(root -> last + 'a'));
        dfs(root -> children[root -> last]);
    }
    ans.pb('-');
}


void uwu(){
    int n; cin >> n;
    vector<string> str(n);
    for(int i =0;i<n;i++)
    {
        cin >> str[i];
    }
    trie t;
    trav(i, str) trie_add(&t, i);
    dfs(&t);
    while(ans.back() == '-') ans.pop_back();
    cout << sz(ans) << "\n";
    trav(i, ans) cout << i << "\n";
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    // cin>>t;
    while(t--){
        uwu();
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 324 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 1216 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1984 KB Output is correct
2 Correct 4 ms 2388 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6476 KB Output is correct
2 Correct 18 ms 13700 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 16036 KB Output is correct
2 Correct 9 ms 4052 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 39952 KB Output is correct
2 Correct 120 ms 91080 KB Output is correct
3 Correct 61 ms 47808 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 31352 KB Output is correct
2 Correct 135 ms 108448 KB Output is correct
3 Correct 67 ms 54244 KB Output is correct
4 Correct 143 ms 102432 KB Output is correct