oj.uz

Submission #992380

# Submission time Handle Problem Language Result Execution time Memory
992380 2024-06-04T11:06:31 Z n3rm1n Type Printer (IOI08_printer) C++17
100 / 100
 135 ms 108484 KB 
#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

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 3 ms 2140 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2648 KB Output is correct
2 Correct 4 ms 3160 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7260 KB Output is correct
2 Correct 18 ms 14424 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16524 KB Output is correct
2 Correct 10 ms 4856 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 40088 KB Output is correct
2 Correct 116 ms 91260 KB Output is correct
3 Correct 63 ms 48076 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31432 KB Output is correct
2 Correct 135 ms 108484 KB Output is correct
3 Correct 71 ms 54480 KB Output is correct
4 Correct 122 ms 102600 KB Output is correct