oj.uz

Submission #226416

# Submission time Handle Problem Language Result Execution time Memory
226416 2020-04-23T18:33:39 Z inluminas Type Printer (IOI08_printer) C++14
100 / 100
 160 ms 49900 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++)
    {
        scanf("%s",s);
        insert();
    }
    getdepth(1);
    dfs(1);
    int sz=ans.size();
    while(ans[sz-1]=='-') sz--;
    printf("%d\n",sz);
    for(int i=0;i<sz;i++) printf("%c\n",ans[i]); 
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",s);
         ~~~~~^~~~~~~~

Subtask #1
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 #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 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 4 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 840 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 8 ms 1460 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3200 KB Output is correct
2 Correct 25 ms 6520 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 18544 KB Output is correct
2 Correct 135 ms 41964 KB Output is correct
3 Correct 76 ms 21744 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14576 KB Output is correct
2 Correct 160 ms 49900 KB Output is correct
3 Correct 96 ms 24688 KB Output is correct
4 Correct 146 ms 47080 KB Output is correct