oj.uz

Submission #291282

# Submission time Handle Problem Language Result Execution time Memory
291282 2020-09-05T04:21:45 Z lemondeath Type Printer (IOI08_printer) C++14
100 / 100
 217 ms 50680 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);
        }
    }

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

    void dfs(string longest, int depth, bool mainBranch) {
        if (!children.empty()) {
            trav(it, children) {
                if (it.first != longest[depth] || !mainBranch) {
                    dfs2(longest, depth, false, it.first);
                }
            }
            if (mainBranch) dfs2(longest, depth, true, longest[depth]);
        }
    }

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

int N, longestLength;
string longestWord;
Trie T;

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

    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 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
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 #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3200 KB Output is correct
2 Correct 27 ms 6520 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7544 KB Output is correct
2 Correct 14 ms 1920 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 18552 KB Output is correct
2 Correct 185 ms 42616 KB Output is correct
3 Correct 117 ms 22128 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 14456 KB Output is correct
2 Correct 217 ms 50680 KB Output is correct
3 Correct 131 ms 25208 KB Output is correct
4 Correct 192 ms 47864 KB Output is correct