Submission #466332

#	Time	Username	Problem	Language	Result	Execution time	Memory
466332		MohamedAliSaidane	Type Printer (IOI08_printer)	C++14	100 / 100	231 ms	121660 KiB

printer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

#define pb push_back
#define popb pop_back
#define all(v) (v).begin(),(v).end()
#define ff first
#define ss second

const ll INF = 1e18;

int n;
vector<string> v;
vector<char> operations;
struct node
{
    char c;
    bool exist;
    int depth = 0;
    vector<node*> child;
    node(char a): c(a), exist(false),depth(0){child.assign(26,NULL);}

};
node* root = new node('!');
void ins(string word)
{
    node* cur = root;
    for(int i = 0; i < word.size(); i ++)
    {
        int alphaNum = word[i] - 'a';
        if(cur ->child[alphaNum] == NULL)
            cur->child[alphaNum] = new node(word[i]);
        cur = cur->child[alphaNum];
    }
    cur->exist = true;
}
int dfs(node *cur)
{
    int maxt = -1;
    bool term =false;
    for(int u = 0; u < 26; u ++)
    {
        if(cur->child[u] == NULL)
            continue;
        maxt = max(maxt,dfs(cur->child[u]));
    }
    cur->depth = maxt + 1;
    return maxt + 1;
}
void printer(node *cur, bool flag)
{
    if(cur->c != '!')
        operations.pb(cur->c);
    if(cur->exist)
        operations.pb('P');
    int maxt = -1;
    int pq = 0;
    for(int u = 0; u < 26; u ++)
    {
        if(cur->child[u] == NULL)
            continue;
        if(cur->child[u]->depth > maxt)
        {
            maxt = cur->child[u]->depth;
            pq = u;
        }
    }
    if(maxt == -1)
    {
        if(!flag)
        operations.pb('-');
        return ;
    }
    for(int u = 0; u < 26; u ++)
    {
        if(cur->child[u] == NULL || u == pq)
            continue;
        printer(cur->child[u],false);
    }
    if(cur->c == '!')
        printer(cur->child[pq],true);
    else
        printer(cur->child[pq],flag);
    if(!flag && cur->c != '!')
    operations.pb('-');
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i <n; i ++)
    {
        string str; cin >> str;
        ins(str);
        v.pb(str);
    }
    dfs(root);
    printer(root,false);
    cout << operations.size() << '\n';
    for(auto e: operations)
        cout << e << '\n';
}

Compilation message (stderr)

printer.cpp: In function 'void ins(std::string)':
printer.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < word.size(); i ++)
      |                    ~~^~~~~~~~~~~~~
printer.cpp: In function 'int dfs(node*)':
printer.cpp:52:10: warning: unused variable 'term' [-Wunused-variable]
   52 |     bool term =false;
      |          ^~~~

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