oj.uz

Submission #226418

# Submission time Handle Problem Language Result Execution time Memory
226418 2020-04-23T18:38:49 Z inluminas Type Printer (IOI08_printer) C++14
100 / 100
 195 ms 49896 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
const int lmt=1e6;
int adj[lmt][26];
char s[lmt];//string s;
vector<char>ans;
int indx=1;
bool linend[lmt];
int depth[lmt];
void insert()
{
    int now=1;
    int sz=strlen(s);
    for(int i=0;i<sz;i++)
    {
        int num=s[i]-'a';
        if(!adj[now][num])
        {
            indx++;
            adj[now][num]=indx;
        }
        now=adj[now][num];
    }
    linend[now]=1;
}
void getdepth(int now)
{
    depth[now]=1;
    for(int i=0;i<26;i++)
    {
        if(adj[now][i])
        {
            getdepth(adj[now][i]);
            depth[now]=max(depth[now],depth[adj[now][i]]+1);
        }
    }
}
void dfs(int now)
{
    int sz=0;
    vector<pair<int,int>>p;
    if(linend[now])
    {
        linend[now]=0;
        ans.push_back('P');
    }
    for(int i=0;i<26;i++)
    {
        if(adj[now][i])
        {
            p.push_back(make_pair(depth[adj[now][i]],i));
            sz++;
        }
    }
    sort(p.begin(),p.end());
    for(int i=0;i<sz;i++)
    {
        char c='a'+p[i].second;
        ans.push_back(c);
        dfs(adj[now][p[i].second]);
        ans.push_back('-');
    }
}
int main()
{
    //#ifndef ONLINE_JUDGE
    //    freopen("take.in","r",stdin);
    //    freopen("give.out","w",stdout);
    //#endif
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        insert();
    }
    getdepth(1);
    dfs(1);
    int sz=ans.size();
    while(ans[sz-1]=='-') sz--;
    cout<<sz<<endl;
    for(int i=0;i<sz;i++) cout<<ans[i]<<endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1152 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3200 KB Output is correct
2 Correct 28 ms 6528 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7676 KB Output is correct
2 Correct 19 ms 1920 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 18544 KB Output is correct
2 Correct 159 ms 42084 KB Output is correct
3 Correct 96 ms 21748 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 14576 KB Output is correct
2 Correct 195 ms 49896 KB Output is correct
3 Correct 108 ms 24560 KB Output is correct
4 Correct 171 ms 47084 KB Output is correct