oj.uz

Submission #931366

# Submission time Handle Problem Language Result Execution time Memory
931366 2024-02-21T16:35:42 Z rahidilbayramli Type Printer (IOI08_printer) C++17
30 / 100
 50 ms 56300 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;
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

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.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Incorrect 5 ms 2908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 7512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 18952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 56300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 56148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -