oj.uz

Submission #932001

# Submission time Handle Problem Language Result Execution time Memory
932001 2024-02-22T19:10:32 Z rahidilbayramli Type Printer (IOI08_printer) C++17
100 / 100
 110 ms 113320 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define pb push_back
#define f first
#define s second

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

vector<char>res;
string maxs;
struct triee{
    struct tr{
        ll a[26];
        tr(ll x = -1){
            memset(a, x, sizeof(a));
        }
    };
    vector<tr>v;
    vl vis;
    triee() : v({tr()}), vis({0}) {}

    void add(string s)
    {
        ll node = 0;
        for(auto u : s)
        {
            ll ch = u - 'a';
            if(v[node].a[ch] == -1)
            {
                v[node].a[ch] = (ll)v.size();
                v.pb(tr());
                vis.pb(0LL);
            }
            node = v[node].a[ch];
        }
        vis[node] = 1;
    }
    void dfs(ll node, ll depth = 0)
    {
        if(vis[node])
        {
            res.pb('P');
            vis[node] = 0;
        }
        if(depth == maxs.size())
            return;
        ll ch = maxs[depth] - 'a';
        for(ll i = 0; i < 26; i++)
        {
            if(i != ch && v[node].a[i] != -1)
            {
                res.pb(i+'a');
                dfs(v[node].a[i], depth+1);
                res.pb('-');
            }
        }
        if(v[node].a[ch] != -1)
        {
            res.pb(ch+'a');
            dfs(v[node].a[ch], depth+1);
            res.pb('-');
        }
    }
} y;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests = 1;
    //cin >> tests;
    while(tests--)
    {
        ll n, i;
        cin >> n;
        for(i = 0; i < n; i++)
        {
            string s;
            cin >> s;
            if(s.size() > maxs.size())
                maxs = s;
            y.add(s);
        }
        y.dfs(0LL, 0LL);
        while(res.back() == '-')
            res.pop_back();
        cout << (ll)res.size() << "\n";
        for(auto u : res)
            cout << u << "\n";
    }
}

Compilation message

printer.cpp: In member function 'void triee::dfs(long long int, long long int)':
printer.cpp:57:18: 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]
   57 |         if(depth == maxs.size())
      |            ~~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 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 600 KB Output is correct
2 Correct 2 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 3 ms 3932 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7636 KB Output is correct
2 Correct 14 ms 16084 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15052 KB Output is correct
2 Correct 8 ms 4960 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 58060 KB Output is correct
2 Correct 97 ms 113200 KB Output is correct
3 Correct 49 ms 58060 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 30104 KB Output is correct
2 Correct 110 ms 113320 KB Output is correct
3 Correct 52 ms 56776 KB Output is correct
4 Correct 90 ms 112844 KB Output is correct