Submission #992380

#	Time	Username	Problem	Language	Result	Execution time	Memory
992380		n3rm1n	Type Printer (IOI08_printer)	C++17	100 / 100	135 ms	108484 KiB

printer

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int MAXN = 25005;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
int n;
string s[MAXN];
struct Node
{
    int is_end, depth;
    Node* p[27];
    Node* par;
    Node()
    {
        is_end = 0;
        depth = 1;
        for (int i = 0; i <= 26; ++ i)
            p[i] = NULL;
    }

};
void insertw(string t, Node* root)
{
    Node* node = root;
    for (int i = 0; i < t.size(); ++ i)
    {
        int s = (t[i] - 'a');
        if(node -> p[s] == NULL) node -> p[s] = new Node;
        node = node -> p[s];
    }
    node -> is_end = 1;
}
void calc_depth(Node* node)
{
    node -> depth = 1;
    Node* nb;
    for (int i = 0; i < 26; ++ i)
    {
        nb = node -> p[i];
        if(nb != NULL)
        {
            calc_depth(nb);
        node -> depth = max(node -> depth, nb -> depth + 1);
        }
    }
}
Node* root;
vector < char > g;
bool cmp(pair < int, Node* > p1, pair < int, Node* > p2)
{
    if(p1.first != p2.first)
        return (p1.first < p2.first);
    return true;
}
void dfs(Node* beg)
{
    if(beg -> is_end == 1)
    {
        g.push_back('P');
    }
    vector < pair < int, int > > nbs;
    for (int i = 0; i < 26; ++ i)
    {
        if(beg -> p[i] != NULL)
        {
            nbs.push_back(make_pair(beg -> p[i] -> depth, i));
        }
    }
    sort(nbs.begin(), nbs.end());
    for (int i = 0; i < nbs.size(); ++ i)
    {
        g.push_back((char)('a' + nbs[i].second));
        dfs(beg -> p[nbs[i].second]);
    }
    g.push_back('-');
}
void read()
{
    root = new Node;
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> s[i];
        insertw(s[i], root);
    }
    //cout << "here 1" << endl;
    calc_depth(root);
    //cout << "here 2" << endl;
    dfs(root);

    while(g.back() == '-')g.pop_back();
    cout << g.size() << endl;
    for (int i = 0; i < g.size(); ++ i)
        cout << g[i] << endl;
}
int main()
{
    speed();
    read();
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void insertw(std::string, Node*)':
printer.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < t.size(); ++ i)
      |                     ~~^~~~~~~~~~
printer.cpp: In function 'void dfs(Node*)':
printer.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i = 0; i < nbs.size(); ++ i)
      |                     ~~^~~~~~~~~~~~
printer.cpp: In function 'void read()':
printer.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i = 0; i < g.size(); ++ i)
      |                     ~~^~~~~~~~~~

• 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