oj.uz

Submission #531352

# Submission time Handle Problem Language Result Execution time Memory
531352 2022-02-28T13:44:53 Z jenkinsser Type Printer (IOI08_printer) C++17
20 / 100
 64 ms 39096 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 sz;
    bool endOfWord = false;
};

typedef node* pnode;

pnode new_node(){
    pnode nd = new node;
    nd->sz = 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->sz++;
    }
    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]->sz,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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 312 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 15712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 39096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 30580 KB Output isn't correct
2 Halted 0 ms 0 KB -