Submission #1270156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270156		ngocphu	Type Printer (IOI08_printer)	C++20	100 / 100	139 ms	139556 KiB

printer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const long long INF = 2000000000000000000LL;
const int maxN = 5e5 + 4;
const int LOG = 18;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
const int MOD = 1e9 + 7;
const int base = 311;

int n;
string str[25001];
vector<char> ans;

struct Node
{
    Node *child[26];
    bool mark, is_end;
    vector<Node*> E;
    char A;

    Node()
    {
        E.clear();
        A = 'a';
        mark = is_end = false;
        for (int i = 0; i < 26; ++i) child[i] = nullptr;
    }
};

struct cmp
{
    bool operator() (string a, string b)
    {
        return a.length() < b.length();
    }
};

Node *root;
Node nodes[maxN];
int cnt = 0;

Node *build()
{
    return &nodes[++cnt];
}

void add(const string &s)
{
    Node *p = root;
    for (int i = 0; i < s.size(); ++i)
    {
        int c = s[i] - 'a';

        if (p->child[c] == nullptr)
        {
            p->child[c] = build();
            p->E.push_back(p->child[c]);
            p->child[c]->A = s[i];
        }

        p = p->child[c];
    }

    p->is_end = true;
}

void dfs(Node *u, Node *par)
{
    if (u != root)
    {
        ans.push_back(u->A);
        if (u->is_end == true) ans.push_back('P');
    }
    Node *p = nullptr;
    for (Node *v : u->E)
    {
        if (v->mark == true)
        {
            p = v;
            continue;
        }

        if (v != par) dfs(v, u);
    }

    if (p != nullptr) dfs(p, u);

    ans.push_back('-');
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    // freopen(".INP","r",stdin);
    // freopen(".OUT","w",stdout);

    root = build();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> str[i];
        add(str[i]);
    }

    sort(str + 1, str + n + 1, cmp());

    Node *p = root;
    for (int i = 0; i < str[n].size(); ++i)
    {
        int c = str[n][i] - 'a';
        p = p->child[c];
        p->mark = true;
    }

    dfs(root, root);

    while(ans.back() == '-') ans.pop_back();

    cout << ans.size() << "\n";

    for (char x : ans) cout << x << "\n";

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