oj.uz

Submission #390201

# Submission time Handle Problem Language Result Execution time Memory
390201 2021-04-15T14:44:41 Z parsabahrami Type Printer (IOI08_printer) C++17
100 / 100
 183 ms 53456 KB 
/* 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 332 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3532 KB Output is correct
2 Correct 24 ms 6980 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 8128 KB Output is correct
2 Correct 10 ms 2128 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 19672 KB Output is correct
2 Correct 155 ms 44984 KB Output is correct
3 Correct 89 ms 23520 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15452 KB Output is correct
2 Correct 183 ms 53456 KB Output is correct
3 Correct 100 ms 26596 KB Output is correct
4 Correct 132 ms 50360 KB Output is correct