oj.uz

Submission #381313

# Submission time Handle Problem Language Result Execution time Memory
381313 2021-03-25T03:54:56 Z jlallas384 Type Printer (IOI08_printer) C++17
100 / 100
 226 ms 51680 KB 
#include <bits/stdc++.h>
using namespace std;

int nxt[500500][26];
int lst[500500];
int dep[500500];
int sz = 1;
vector<char> ans;
void add(string s){
    int cur = 0;
    for(int i = 0; i < (int) s.size(); i++){
        int c = s[i] - 'a';
        if(!nxt[cur][c]) nxt[cur][c] = sz++;
        cur = nxt[cur][c];
    }
    lst[cur] = true;
}

void dfs1(int v){
    for(int i = 0; i < 26; i++) if(nxt[v][i]){
        dfs1(nxt[v][i]);
        dep[v] = max(dep[v],dep[nxt[v][i]]+1);
    }
}

void dfs2(int v){
    vector<pair<int,int>> ord; //(max hi,v);
    for(int i = 0; i < 26; i++) if(nxt[v][i]){
        ord.emplace_back(dep[nxt[v][i]],i);
    }
    sort(ord.begin(), ord.end());
    for(auto [hi,i]: ord){
        ans.push_back(i + 'a');
        if(lst[nxt[v][i]]) ans.push_back('P');
        dfs2(nxt[v][i]);
        ans.push_back('-');
    }
}

int main(){
    int n;
    cin >> n;
    while(n--){
        string s;
        cin >> s;
        add(s);
    }
    dfs1(0);
    dfs2(0);
    while(ans.back() != 'P') ans.pop_back();
    cout << ans.size() << '\n';
    for(char x: ans){
        cout << x << "\n";
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1132 KB Output is correct
2 Correct 7 ms 1388 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3308 KB Output is correct
2 Correct 28 ms 6764 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7912 KB Output is correct
2 Correct 15 ms 2028 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 19300 KB Output is correct
2 Correct 192 ms 43488 KB Output is correct
3 Correct 107 ms 22628 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15076 KB Output is correct
2 Correct 226 ms 51680 KB Output is correct
3 Correct 119 ms 25700 KB Output is correct
4 Correct 197 ms 48864 KB Output is correct