oj.uz

Submission #589783

# Submission time Handle Problem Language Result Execution time Memory
589783 2022-07-05T09:14:53 Z proma Type Printer (IOI08_printer) C++17
20 / 100
 51 ms 18720 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], 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());
    }
}

string ans = "";

void dfs(int v) {
    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]);
    }
    else {
        ans += "P";
    }
    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 1 ms 452 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #2
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 #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 1 ms 340 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1236 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3280 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 7776 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 18720 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 14680 KB didn't print every word
2 Halted 0 ms 0 KB -