oj.uz

Submission #863276

# Submission time Handle Problem Language Result Execution time Memory
863276 2023-10-20T00:56:41 Z HuyQuang_re_Zero Type Printer (IOI08_printer) C++14
100 / 100
 134 ms 98568 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 100005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define rand(l,r) (l+rng()%(r-l+1))
using namespace std;
string s,x;
int n,i,pos,sum,node;
struct trie
{
    int last,endn;
    trie *c[26];
} *u,*r;
void DFS(trie *u)
{
    if(u->endn) cout<<"P"<<'\n';
    int k=-1;
    trie *x=NULL;
    for(int i=0;i<26;i++)
        if(u->c[i]!=NULL && u->c[i]->last) k=i,x=u->c[i];
    for(int i=0;i<26;i++)
        if(u->c[i]!=NULL && u->c[i]!=x)
        {
            cout<<char(i+'a')<<'\n';
            DFS(u->c[i]);
            cout<<"-"<<'\n';
        }

    if(x!=NULL)
    {
        cout<<char(k+'a')<<'\n';
        DFS(x);
    }
    else if(u->last) exit(0);
}
int main()
{
  //  freopen("type_printer.inp","r",stdin);
  //  freopen("type_printer.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    r=new trie();
    for(i=1;i<=n;i++)
    {
        cin>>s;
        u=r;
        for(char ch:s)
        {
            if(u->c[ch-'a']==NULL) u->c[ch-'a']=new trie(),node++;
            u=u->c[ch-'a'];
        }
        u->endn=1;
        if(x.size()<s.size()) x=s,pos=i;
        sum+=s.size();
    }
    u=r;
    for(char ch:x) u=u->c[ch-'a'],u->last=1;
    cout<<2*node-x.size()+n<<'\n';
    DFS(r);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5980 KB Output is correct
2 Correct 15 ms 12380 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14680 KB Output is correct
2 Correct 5 ms 3420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 36176 KB Output is correct
2 Correct 134 ms 82828 KB Output is correct
3 Correct 57 ms 42836 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 28252 KB Output is correct
2 Correct 116 ms 98568 KB Output is correct
3 Correct 57 ms 48472 KB Output is correct
4 Correct 104 ms 93148 KB Output is correct