oj.uz

Submission #932006

# Submission time Handle Problem Language Result Execution time Memory
932006 2024-02-22T19:24:41 Z rahidilbayramli Type Printer (IOI08_printer) C++17
100 / 100
 96 ms 113336 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));
        }
    };
    vl vis;
    vector<tr>v;
    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)
    {
        if(vis[node])
        {
            res.pb('P');
            vis[node] = 0;
        }
        if(depth == (ll)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 constructor 'triee::triee()':
printer.cpp:32:15: warning: 'triee::v' will be initialized after [-Wreorder]
   32 |     vector<tr>v;
      |               ^
printer.cpp:31:8: warning:   'std::vector<long long int> triee::vis' [-Wreorder]
   31 |     vl vis;
      |        ^~~
printer.cpp:33:5: warning:   when initialized here [-Wreorder]
   33 |     triee() : v({tr()}), vis({0}) {}
      |     ^~~~~

Subtask #1
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 #2
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 #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 1 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 3 ms 2208 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8152 KB Output is correct
2 Correct 13 ms 16236 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 57544 KB Output is correct
2 Correct 92 ms 113176 KB Output is correct
3 Correct 48 ms 57088 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 29388 KB Output is correct
2 Correct 96 ms 111800 KB Output is correct
3 Correct 57 ms 57036 KB Output is correct
4 Correct 85 ms 113336 KB Output is correct