oj.uz

Submission #466332

# Submission time Handle Problem Language Result Execution time Memory
466332 2021-08-18T18:21:08 Z MohamedAliSaidane Type Printer (IOI08_printer) C++14
100 / 100
 231 ms 121660 KB 
#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

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 272 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 1228 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2124 KB Output is correct
2 Correct 5 ms 2636 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7244 KB Output is correct
2 Correct 30 ms 15332 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 18084 KB Output is correct
2 Correct 13 ms 4420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 45284 KB Output is correct
2 Correct 198 ms 102332 KB Output is correct
3 Correct 105 ms 53812 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 35636 KB Output is correct
2 Correct 231 ms 121660 KB Output is correct
3 Correct 122 ms 61112 KB Output is correct
4 Correct 209 ms 115036 KB Output is correct