Submission #931366

#	Time	Username	Problem	Language	Result	Execution time	Memory
931366		rahidilbayramli	Type Printer (IOI08_printer)	C++17	30 / 100	50 ms	56300 KiB

printer

#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;
const ll sz = 1e5+5;
ll triee[sz][26], value[sz], subtree[sz], next_node = 1;
map<ll, char>mp;
vector<char>res;
void add(string& s, ll id)
{
    ll node = 0;
    for(ll idx = 0; idx < s.size(); idx++)
    {
        ll ch = s[idx] - 'a';
        if(!triee[node][ch]){
            triee[node][ch] = next_node;
            mp[next_node] = s[idx];
            next_node++;
        }
        node = triee[node][ch];
    }
    value[node] = 1;
}
void dfs1(ll node = 0)
{
    subtree[node] = 1;
    for(ll i = 0; i < 26; i++)
    {
        if(triee[node][i]){
            dfs1(triee[node][i]);
            subtree[node] += subtree[triee[node][i]];
        }
    }
}
void dfs(ll node = 0)
{
    if(node)
        res.pb(mp[node]);
    if(value[node])
        res.pb('P');
    vector<pll>vv;
    for(ll i = 0; i < 26; i++)
    {
        if(triee[node][i])
            vv.pb({subtree[triee[node][i]], triee[node][i]});
    }
    sort(all(vv));
    for(ll i = 0; i < vv.size(); i++)
        dfs(vv[i].s);
    res.pb('-');
}
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 = 1; i <= n; i++)
        {
            string s;
            cin >> s;
            add(s, i);
        }
        dfs1();
        dfs();
        while(res.back() == '-')
            res.pop_back();
        cout << res.size() << "\n";
        for(auto u : res)
            cout << u << "\n";
    }
}

Compilation message (stderr)

printer.cpp: In function 'void add(std::string&, long long int)':
printer.cpp:24:25: 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]
   24 |     for(ll idx = 0; idx < s.size(); idx++)
      |                     ~~~~^~~~~~~~~~
printer.cpp: In function 'void dfs(long long int)':
printer.cpp:60:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(ll i = 0; i < vv.size(); i++)
      |                   ~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10