Submission #114659

#	Time	Username	Problem	Language	Result	Execution time	Memory
114659		zubec	Type Printer (IOI08_printer)	C++14	100 / 100	205 ms	58716 KiB

printer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int n;

struct trie{
    int term;
    int nxt[26];
};

trie t[500100];

int tin[500100], tout[500100], pr[500100], tim, mxdeep[500100];

int kol = 0;

void dfs(int v, int deep){
    tin[v] = ++tim;
    mxdeep[v] = deep;
    for (int i = 0; i < 26; i++){
        if (t[v].nxt[i] != 0){
            pr[t[v].nxt[i]] = v;
            dfs(t[v].nxt[i], deep+1);
            mxdeep[v] = max(mxdeep[v], mxdeep[t[v].nxt[i]]);
        }
    }

    tout[v] = tim;
}

bool cmp(int a, int b){
    return mxdeep[a] < mxdeep[b];
}

bool ifpred(int a, int b){
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lst = -1;

int deep = 0;

string s[25100];

vector <char> ansvec;

void dfs2(int v){
    if (t[v].term){
        int id = t[v].term;
        if (lst == -1){
            for (int j = 0; j < s[id].size(); j++){
                ansvec.push_back(s[id][j]);
            }
            deep = s[id].size();
            lst = v;
        } else {
            while(!ifpred(lst, v)){
                lst = pr[lst];
                --deep;
                ansvec.push_back('-');
            }
            while(deep < s[id].size()){
                ansvec.push_back(s[id][deep]);
                ++deep;
            }
            lst = v;
        }
        ansvec.push_back('P');
    }
    vector <int> vec;
    for (int i = 0; i < 26; i++){
        if (t[v].nxt[i] != 0){
            vec.push_back(t[v].nxt[i]);
        }
    }
    sort(vec.begin(), vec.end(), cmp);
    for (int i = 0; i < vec.size(); i++)
        dfs2(vec[i]);
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++){
        string s;
        cin >> s;
        int v = 0;
        for (int j = 0; j < s.size(); j++){
            if (t[v].nxt[s[j]-'a'] == 0){
                t[v].nxt[s[j]-'a'] = ++kol;
            }
            v = t[v].nxt[s[j]-'a'];
        }
        t[v].term = i;
        ::s[i] = s;
    }
    dfs(0, 0);
    dfs2(0);

    cout << ansvec.size() << "\n";
    for (int i = 0; i < ansvec.size(); i++)
        cout << ansvec[i] << "\n";

}

Compilation message (stderr)

printer.cpp: In function 'void dfs2(int)':
printer.cpp:53:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < s[id].size(); j++){
                             ~~^~~~~~~~~~~~~~
printer.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(deep < s[id].size()){
                   ~~~~~^~~~~~~~~~~~~~
printer.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++)
                     ~~^~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:92:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < s.size(); j++){
                         ~~^~~~~~~~~~
printer.cpp:105:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ansvec.size(); i++)
                     ~~^~~~~~~~~~~~~~~

• 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