oj.uz

Submission #1094632

# Submission time Handle Problem Language Result Execution time Memory
1094632 2024-09-30T07:26:16 Z Dan4Life Type Printer (IOI08_printer) C++17
100 / 100
 195 ms 93108 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxS = 25000*21;
int n, cnt;
vector<char> ans;
int trieNode = 0;
int trie[27][mxS];
int dep[27][mxS];
bitset<mxS> word;

void add(string s){
    int v = 0;
    for(auto u : s){
        int c = u-'a';
        if(!trie[c][v])
            trie[c][v] = ++trieNode;
        dep[c][v]=max(dep[c][v],sz(s));
        v = trie[c][v];
    }
    word[v]=1;
}

void dfs(int s){
    if(word[s]) ans.pb('P'),cnt++;
    vector<int> ord(26,0); iota(all(ord),0);
    sort(all(ord),[&](int a, int b){
        return dep[a][s]<dep[b][s];
    });
    for(int c : ord){
        if(!trie[c][s]) continue;
        ans.pb(char('a'+c));
        dfs(trie[c][s]);
    }
    if(cnt!=n) ans.pb('-');
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++){
        string s; cin >> s; add(s);
    }
    dfs(0); cout << sz(ans) << "\n";
    for(auto u : ans) cout << u << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 472 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6092 KB Output is correct
2 Correct 25 ms 12200 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 14020 KB Output is correct
2 Correct 11 ms 3628 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 34252 KB Output is correct
2 Correct 156 ms 78292 KB Output is correct
3 Correct 81 ms 40644 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 26836 KB Output is correct
2 Correct 195 ms 93108 KB Output is correct
3 Correct 90 ms 46168 KB Output is correct
4 Correct 137 ms 88008 KB Output is correct