oj.uz

Submission #540684

# Submission time Handle Problem Language Result Execution time Memory
540684 2022-03-21T12:11:51 Z csamoila Type Printer (IOI08_printer) C++14
100 / 100
 164 ms 99640 KB 
#include <bits/stdc++.h>

using namespace std;

ifstream fin("input.in");
ofstream fout("input.out");

int N;
string V[101];

struct TrieNode{
    int nrcuv,nrfii;
    TrieNode *fii[26];
    TrieNode(){
        nrcuv=nrfii=0;
        for(int i=0;i<26;i++)
            fii[i]=0;
    }
};

TrieNode *root = new TrieNode;

void inserare(TrieNode *nod,char *s){
    if(*s==0){
        nod->nrcuv++;
        return;
    }
    if(nod->fii[*s-'a']==0){
        nod->nrfii++;
        nod->fii[*s-'a'] = new TrieNode;
    }

    inserare(nod->fii[*s-'a'],s+1);
}

char cuvmax[21];

int rez;
int cont;

string S;

void f(TrieNode *nod,string s,char *cuv,int ok){
    int p=-1;
    for(int i=0;i<26;i++){
        if(nod->fii[i]==0) continue;
        if((char)(i+'a')==*cuv and ok==1){
            p=i;
            continue;
        }
        S+=(char)(i+'a');
        if(nod->fii[i]->nrcuv!=0)
            S+='P',nod->fii[i]->nrcuv=0,cont++;
        f(nod->fii[i],s+(char)(i+'a'),cuv+1,0);
        if(cont<N) S+='-';
    }
    if(p!=-1){
    if(nod->fii[p]==0) return;
    S+=(char)(p+'a');
    if(nod->fii[p]->nrcuv!=0)
        S+='P',cont++;
    f(nod->fii[p],s+(char)(p+'a'),cuv+1,1);
    if(cont<N) S+='-';
    }
}

int main()
{
    cin >> N;
    for(int i=1;i<=N;i++){
        char s[21];
        cin >> s;
        inserare(root,s);
        if(strlen(s)>strlen(cuvmax))
            strcpy(cuvmax,s);
    }
    f(root,"",cuvmax,1);
    cout << S.size() << '\n';
    for(auto it:S) cout << it << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5996 KB Output is correct
2 Correct 24 ms 12496 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 14692 KB Output is correct
2 Correct 11 ms 3412 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 36632 KB Output is correct
2 Correct 136 ms 83724 KB Output is correct
3 Correct 85 ms 43112 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 28596 KB Output is correct
2 Correct 164 ms 99640 KB Output is correct
3 Correct 92 ms 49052 KB Output is correct
4 Correct 144 ms 94016 KB Output is correct