oj.uz

Submission #788154

# Submission time Handle Problem Language Result Execution time Memory
788154 2023-07-19T20:30:10 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 149 ms 79468 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
const int D = 26;

int trie[N][D];
int node = 1;
bool fin[N];
bool vis[N];
vector<char> ans;

int great;
int low[N];
priority_queue<tuple<int, int, char>> G[N];

void add(string s){
    int cur = 0;
    for(char ch : s){
        int c = ch - 'a';
        if(!trie[cur][c]){
            trie[cur][c] = node;
            node++;
        }
        cur = trie[cur][c];
    }
    fin[cur] = 1;
}

void produndidad(int cur){
    if(fin[cur]) ans.push_back('P');
    
    while(!G[cur].empty()){
        int hijo;
        char c;
        tie(great, hijo, c) = G[cur].top();
        G[cur].pop();

        ans.push_back(c);
        produndidad(hijo);
        ans.push_back('-');
    }
}

void dfs(int cur, int he){
    vis[cur] = 1;
    low[cur] = he;
    for(int c = 0; c < 26; c++){
        if(trie[cur][c] and !vis[trie[cur][c]]){
            dfs(trie[cur][c], he+1);
            int child = trie[cur][c];
            G[cur].push({-low[child], child, c+'a'});
            low[cur] = max(low[cur], low[child]);
        }
    }
}
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        add(s);
    }
    dfs(0, 0);
    produndidad(0);
    cout << ans.size() + great << "\n";
    for(int i = 0; i < (int)ans.size() + great; i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 8 ms 15968 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 8 ms 15972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15936 KB Output is correct
2 Correct 8 ms 15968 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16048 KB Output is correct
2 Correct 9 ms 16468 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16876 KB Output is correct
2 Correct 13 ms 17232 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19636 KB Output is correct
2 Correct 30 ms 23880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25124 KB Output is correct
2 Correct 17 ms 18048 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 38976 KB Output is correct
2 Correct 125 ms 69316 KB Output is correct
3 Correct 75 ms 43336 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 33812 KB Output is correct
2 Correct 149 ms 79468 KB Output is correct
3 Correct 83 ms 47044 KB Output is correct
4 Correct 131 ms 76092 KB Output is correct