oj.uz

Submission #589811

# Submission time Handle Problem Language Result Execution time Memory
589811 2022-07-05T09:56:22 Z proma Type Printer (IOI08_printer) C++17
100 / 100
 141 ms 51716 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1276 KB Output is correct
2 Correct 3 ms 1492 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3412 KB Output is correct
2 Correct 19 ms 6916 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7976 KB Output is correct
2 Correct 8 ms 2216 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 19100 KB Output is correct
2 Correct 110 ms 43580 KB Output is correct
3 Correct 65 ms 22764 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15084 KB Output is correct
2 Correct 141 ms 51716 KB Output is correct
3 Correct 71 ms 25856 KB Output is correct
4 Correct 118 ms 48940 KB Output is correct