oj.uz

Submission #291263

# Submission time Handle Problem Language Result Execution time Memory
291263 2020-09-05T02:04:57 Z lemondeath Type Printer (IOI08_printer) C++14
10 / 100
 52 ms 18044 KB 
// 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1152 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3072 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 7296 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 18044 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 14208 KB Line "" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -