Submission #291263

#	Time	Username	Problem	Language	Result	Execution time	Memory
291263		lemondeath	Type Printer (IOI08_printer)	C++14	10 / 100	52 ms	18044 KiB

printer

// IOI 2008 (Cairo) Day 1 - Problem 1 - Type Printer
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define PB push_back
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define NMAX (int)(1e5+5)
#define INF 0x3f3f3f
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

struct Trie {
    map<char, Trie> children;
    bool isWord;

    void insert(string s, int pos = 0) {
        if (pos == sz(s)) {
            isWord = true;
        }
        else {
            children[s[pos]].insert(s, pos+1);
        }
    }

    void dfsTest() {
        for (auto& it : children) {
            cout << it.first << endl;
            it.second.dfsTest();
            cout << "-" << it.first << endl;
        }
    }

    int nodeCount() {
        int output = 1;
        trav(it, children) {
            output += it.second.nodeCount();
        }
        return output;
    }

    void dfs(string longest, int depth, bool mainBranch) {
        char c;
        trav(it, children) {
            c = it.first;
            //cout << "depth " << depth << ", now at char " << c << endl;
            if (c != longest[depth]) {
                dfs2(longest, depth, false, c);
                /*
                cout << c << endl;
                if (it.second.isWord) {
                    cout << "P" << endl;
                }
                else {
                    it.second.dfs(longest, depth+1);
                    cout << "finished dfs, now at depth " << depth << ", char " << c << endl;
                }
                cout << "-" << endl;
                //*/
            }
        }
        if (mainBranch) dfs2(longest, depth, true, longest[depth]);
        /*
        c = longest[depth];
        cout << c << endl;
        if (children[c].isWord) {
            cout << "P" << endl;
        }
        else {
            children[c].dfs(longest, depth+1);
        }
        //*/
    }

    void dfs2(string longest, int depth, bool mainBranch, char c) {
        cout << c << endl;
        if (children[c].isWord) {
            cout << "P" << endl;
        }
        else {
            children[c].dfs(longest, depth+1, mainBranch);
        }
        if (c != longest[depth]) {
            cout << "-" << endl;
        }
    }

};

int N, longestLength;
string longestWord;
Trie T;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);

    cin >> N;
    for (int i = 0; i < N; i++) {
        string s; cin >> s;
        T.insert(s);
        if (sz(s) > longestLength) {
            longestWord = s;
            longestLength = sz(s);
        }
    }

    cout << 2*(T.nodeCount()-1) + N - longestLength << endl;
    T.dfs(longestWord, 0, 1);
    //T.dfsTest();


    return 0;
}

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