oj.uz

Submission #321631

# Submission time Handle Problem Language Result Execution time Memory
321631 2020-11-13T00:28:54 Z iliccmarko Type Printer (IOI08_printer) C++14
100 / 100
 123 ms 49004 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
using namespace std;
const int N = 5e5 + 5;
int trie[N][26];
int kraj[N];
int ind;
int n;
int cnt = 0;
vector<string> v;
int m;
string ss;
int c;
vector<int> kk;

void _insert(string s)
{
    int node = 0;
    for(int i = 0;i<len(s);i++)
    {
        int c = s[i] - 'a';
        if(!trie[node][c]) trie[node][c] = ++ind;
        node = trie[node][c];
    }
    kraj[node] = 1;
}
int u;

void search(string s)
{
    int node = 0;
    for(int i = 0;i<len(s);i++)
    {
        int c = s[i] - 'a';
        kk.pb(trie[node][c]);
        node = trie[node][c];
    }
}

void print(int node, int p)
{
    if(kraj[node])
    {
        cnt++;
        cout<<"P"<<endl;
    }
    for(int i = 0;i<26;i++)
    {
        if(i==p) continue;
        if(trie[node][i])
        {
            cout<<char(i+'a')<<endl;
            print(trie[node][i], -1);
            cout<<"-"<<endl;
        }
    }
}


int main()
{
    ios
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        string s;
        cin>>s;
        _insert(s);
        if(len(s)>len(ss))
            ss = s;
    }
    int le = len(ss);
    ss.pb('#');
    cout<<2*ind - le + n<<endl;
    search(ss);
    print(0, ss[0]-'a');
    for(int i = 0;i<le;i++)
    {
        cout<<ss[i]<<endl;
        if(i==le-1) {
            cout<<"P"<<endl;
            break;
        }
        print(kk[i], ss[i+1]-'a');

    }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3052 KB Output is correct
2 Correct 16 ms 6380 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7276 KB Output is correct
2 Correct 8 ms 1900 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 18028 KB Output is correct
2 Correct 102 ms 41196 KB Output is correct
3 Correct 57 ms 21484 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14080 KB Output is correct
2 Correct 123 ms 49004 KB Output is correct
3 Correct 66 ms 24300 KB Output is correct
4 Correct 110 ms 46352 KB Output is correct