Submission #226416

#	Time	Username	Problem	Language	Result	Execution time	Memory
226416		inluminas	Type Printer (IOI08_printer)	C++14	100 / 100	160 ms	49900 KiB

printer

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10