Submission #390201

#	Time	Username	Problem	Language	Result	Execution time	Memory
390201		parsabahrami	Type Printer (IOI08_printer)	C++17	100 / 100	183 ms	53456 KiB

printer

/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 5e5 + 10;
int nxt[26][N], M[N], dp[N], H[N], n, tim, tar; char S[N];
vector<char> ret;

void addtrie(char* x) {
    int v = 0;
    for (int i = 0; x[i]; i++) {
        int c = x[i] - 'a';
        if (!nxt[c][v]) nxt[c][v] = ++tim, H[tim] = H[v] + 1;
        v = nxt[c][v];
    }
    M[v] = 1;
}

void preDFS(int v) {
    dp[v] = (v == tar);
    for (int i = 0; i < 26; i++) 
        if (nxt[i][v]) {
            preDFS(nxt[i][v]); 
            dp[v] |= dp[nxt[i][v]];
        }
}

void DFS(int v) {
    if (M[v]) ret.push_back('P');
    int u = -1;
    for (int i = 0; i < 26; i++) 
        if (nxt[i][v] && !dp[nxt[i][v]]) 
            ret.push_back('a' + i), DFS(nxt[i][v]), ret.push_back('-');
        else if (nxt[i][v]) u = i;
    if (~u) ret.push_back('a' + u), DFS(nxt[u][v]);
}


int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%s", S + 1), addtrie(S + 1);
    tar = max_element(H, H + N) - H;
    preDFS(0);
    DFS(0);
    printf("%d\n", SZ(ret));
    for (char c : ret) printf("%c\n", c);
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
printer.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |         scanf("%s", S + 1), addtrie(S + 1);
      |         ~~~~~^~~~~~~~~~~~~

• 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