oj.uz

Submission #921206

# Submission time Handle Problem Language Result Execution time Memory
921206 2024-02-03T13:47:37 Z Alihan_8 Type Printer (IOI08_printer) C++17
100 / 100
 119 ms 113256 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

vector <char> op;

string t;

struct Trie{
    struct Info{
        int a[26];
        Info(int x = -1){
            memset(a, x, sizeof(a));
        }
    };

    vector <Info> T;
    vector <int> us;
    Trie() : T({Info()}), us({0}) {}

    void ins(string s){
        int rt = 0;
        for ( auto &i: s ){
            int x = i - 'a';
            if ( T[rt].a[x] == -1 ){
                T[rt].a[x] = (int)T.size();
                T.pb(Info());
                us.pb(0);
            } rt = T[rt].a[x];
        }
        us[rt] = true;
    }

    void dfs(int rt, int d){
        if ( us[rt] ){
            us[rt] = false;
            op.pb('P');
        }
        if ( d == t.size() ){
            return;
        }
        int x = t[d] - 'a';
        for ( int i = 0; i < 26; i++ ){
            if ( i != x && T[rt].a[i] != -1 ){
                op.pb(i + 'a');
                dfs(T[rt].a[i], d + 1);
                op.pb('-');
            }
        }
        if ( T[rt].a[x] != -1 ){
            op.pb(x + 'a');
            dfs(T[rt].a[x], d + 1);
            op.pb('-');
        }
    }
} tr;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <string> s(n);
    for ( auto &x: s ){
        cin >> x;
        if ( x.size() > t.size() ){
            t = x;
        } tr.ins(x);
    }
    tr.dfs(0, 0);
    while ( op.back() == '-' ){
        op.pop_back();
    }
    cout << op.size() << ln;
    for ( auto &x: op ){
        cout << x << ln;
    }

//    cout << '\n';
}

Compilation message

printer.cpp: In member function 'void Trie::dfs(long long int, long long int)':
printer.cpp:65:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         if ( d == t.size() ){
      |              ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2208 KB Output is correct
2 Correct 4 ms 3928 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8664 KB Output is correct
2 Correct 15 ms 15824 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 15828 KB Output is correct
2 Correct 7 ms 4384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 57784 KB Output is correct
2 Correct 109 ms 112812 KB Output is correct
3 Correct 60 ms 58048 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 29948 KB Output is correct
2 Correct 119 ms 112560 KB Output is correct
3 Correct 70 ms 58316 KB Output is correct
4 Correct 109 ms 113256 KB Output is correct