Submission #1139094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139094		ymoras	Type Printer (IOI08_printer)	C++17	80 / 100	228 ms	28240 KiB

printer

#include <bits/stdc++.h>
using namespace std;

const int ALPHABET = 26;
const int MAXN = 2e5 + 5;

int trie[MAXN][ALPHABET];
int endW[MAXN];
int marked[MAXN];
int nxt = 1;
vector<char> operations;

void insert(const string& s) {
    int node = 0;
    for (char c : s) {
        int ch = c - 'a';
        if (trie[node][ch] == 0) {
            trie[node][ch] = nxt++;
        }
        node = trie[node][ch];
    }
    endW[node] = 1;
}

void lastPath(const string& s) {
    int node = 0;
    for (char c : s) {
        int ch = c - 'a';
        node = trie[node][ch];
        marked[node] = 1;
    }
}

bool visited[MAXN][ALPHABET];
void dfs(int node) {

    // Primero procesar nodos no marcados
    for (int c = 0; c < ALPHABET; c++) {
        if (trie[node][c] == 0) continue;
        int child = trie[node][c];

        if (!marked[child]) {
        visited[node][c] = 1;

            operations.push_back(c + 'a');
            
            if (endW[child]) {
                operations.push_back('P');

            }
            if (!visited[child][c]) { 
                dfs(child);
                
            }
            
            operations.push_back('-');
        } 
    }
    for (int c = 0; c < ALPHABET; c++) {
        if (trie[node][c] == 0) continue;
        int child = trie[node][c];
        
        if (marked[child]) {
        visited[node][c] = 1;
            operations.push_back(c + 'a');
            if (endW[child]) {
                    operations.push_back('P');
                }
            if (!visited[child][c]){
                dfs(child);
                
            }
            
        }
    }

}


int main() {

    int N;
    cin >> N;
    
    memset(trie, 0, sizeof(trie));
    memset(endW, 0, sizeof(endW));
    memset(marked, 0, sizeof(marked));
    nxt = 1;
    operations.clear();
    
    vector<string> words(N);
    string longestWord;
    
    for (int i = 0; i < N; i++) {
        cin >> words[i];
        insert(words[i]);
        
        if (words[i].length() > longestWord.length()) {
            longestWord = words[i];
        }
    }
    
    lastPath(longestWord);
    
    dfs(0);
    
    cout << operations.size() << endl;
    for (char op : operations) {
        cout << op << endl;
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10