oj.uz

Submission #226417

# Submission time Handle Problem Language Result Execution time Memory
226417 2020-04-23T18:35:28 Z inluminas Type Printer (IOI08_printer) C++14
80 / 100
 1000 ms 49208 KB 
#include<bits/stdc++.h>
using namespace std;
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;//scanf("%s",s);
        insert();
    }
    getdepth(1);
    dfs(1);
    int sz=ans.size();
    while(ans[sz-1]=='-') sz--;
    cout<<sz<<endl;//printf("%d\n",sz);
    for(int i=0;i<sz;i++) cout<<ans[i]<<endl;//printf("%c\n",ans[i]); 
}

Subtask #1
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 #2
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 #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 7 ms 384 KB Output is correct
2 Correct 20 ms 768 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 3192 KB Output is correct
2 Correct 239 ms 6520 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 7668 KB Output is correct
2 Correct 89 ms 1912 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 18720 KB Output is correct
2 Execution timed out 1089 ms 41832 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 14576 KB Output is correct
2 Execution timed out 1093 ms 49208 KB Time limit exceeded
3 Halted 0 ms 0 KB -