oj.uz

Submission #531354

# Submission time Handle Problem Language Result Execution time Memory
531354 2022-02-28T13:49:30 Z jenkinsser Type Printer (IOI08_printer) C++17
100 / 100
 134 ms 106436 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pii pair<int,int>
#define piii pair<int,pii>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define int ll
 
using namespace std;

const int N = 2e5+5;
const int INF = 1e9+5;
const int mod = 1e9+7;

struct node{
    node * letters[26];
    int max_depth;
    bool endOfWord = false;
};

typedef node* pnode;

pnode new_node(){
    pnode nd = new node;
    nd->max_depth = 0;
    nd->endOfWord = false;
    for(int i=0;i<26;i++)
        nd->letters[i] = NULL;
    return nd;
}

void insert(string s,pnode cur){
    for(char c:s){
        if(cur->letters[c-'a'] == NULL)
            cur->letters[c-'a'] = new_node();
        cur = cur->letters[c-'a'];
        cur->max_depth = max(cur->max_depth, (int)s.size());
    }
    cur->endOfWord = true;
}

string ans;

void dfs(pnode v){
    if(v->endOfWord)
        ans += "P";
    vector<pii> order;
    for(int i = 0; i < 26; i++){
        if(v->letters[i] != NULL)
            order.pb({v->letters[i]->max_depth,i});
    }
    sort(all(order));
    for(auto [x,c]:order){
        ans += (char)(c+'a');
        dfs(v->letters[c]);
        ans += '-';
    }
}

int n;

void solve(){
    cin >> n;
    pnode root = new_node();
    for(int i=1;i<=n;i++){
        string s;
        cin >> s;
        insert(s,root);
    }
    dfs(root);
    while(!ans.empty() && ans.back()!='P')
        ans.pop_back();
    cout << ans.size() << nl;
    for(char c:ans)
        cout << c << nl;
}

signed main(){
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
        
    fastio()

    int tt=1;
    // cin >> tt;
    while(tt--)
        solve();
    
    #ifdef LOCAL
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1948 KB Output is correct
2 Correct 3 ms 2380 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6348 KB Output is correct
2 Correct 18 ms 13380 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15712 KB Output is correct
2 Correct 8 ms 3524 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 38892 KB Output is correct
2 Correct 121 ms 89432 KB Output is correct
3 Correct 63 ms 46172 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 30436 KB Output is correct
2 Correct 134 ms 106436 KB Output is correct
3 Correct 69 ms 52324 KB Output is correct
4 Correct 118 ms 100476 KB Output is correct