Submission #589811

#	Time	Username	Problem	Language	Result	Execution time	Memory
589811		proma	Type Printer (IOI08_printer)	C++17	100 / 100	141 ms	51716 KiB

printer

#include <bits/stdc++.h>

//#define int long long
#define see(x) cout<<#x<<"="<<x<<endl;
#define endl "\n"

using namespace std;

const int N = 250005;
const int UP = 5*1e5+5;

int n, s;

// trie

int t[30][UP], lng[UP], f[UP], nxt = 0;

void add(string &word) {
    int cur = 0;
    for (int i = 0; i < word.size(); i ++) {
        int j = word[i] - 97;
        if (!t[j][cur]) t[j][cur] = ++ nxt;
        cur = t[j][cur];
        lng[cur] = max(lng[cur], (int)word.size());
        if (i == int(word.size()) - 1) f[cur] = 1;
    }
}

string ans = "";

void dfs(int v) {
    if (f[v]) {
        ans += "P";
    }
    int mx = 0, to = -1;
    for (int i = 0; i < 26; i ++) {
        if (t[i][v] and mx < lng[t[i][v]]) {
            mx = lng[t[i][v]];
            to = i;
        }
    }
    for (int i = 0; i < 26; i ++) {
        if (to == i) continue;
        if (t[i][v]) {
            char c = i + 97;
            ans += c;
            dfs(t[i][v]);
        }
    }
    if (to != -1) {
        char c = to + 97;
        ans += c;
        dfs(t[to][v]);
    }
    ans += "-";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 0; i < n; i ++) {
        string s;
        cin >> s;
        add(s);
    }

    dfs(0);

    int i;
    for (i = int(ans.size()) - 1; i >= 0; i --) {
        if (ans[i] != '-') break;
    }
    cout << i + 1 << endl;
    for (int j = 0; j <= i; j ++) {
        cout << ans[j] << endl;
    }

    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void add(std::string&)':
printer.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < word.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~

• 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: 10 / 10
• Subtask 10: 10 / 10