oj.uz

Submission #934441

# Submission time Handle Problem Language Result Execution time Memory
934441 2024-02-27T10:24:04 Z bashNewbie Type Printer (IOI08_printer) C++17
100 / 100
 74 ms 50952 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

#define fast_io ios::sync_with_stdio(0), cin.tie(0)

const int N = 5e5+7, K = 26;
int adj[N][K+1], len;
string ms, ret;

inline void pr(char c) {
	ret += c;
}
inline void pr(int c) {
	ret += c+'a';
}

void add(string& s) {
	int x = 0;
	for(char ch: s) {
		int c = ch-'a', y = adj[x][c];
		if(!y) adj[x][c] = ++len;
		x = adj[x][c];
	}
	adj[x][K] = 1;
}

void dfs(int x, int in, int d) {
	int c = in && d < (int)ms.size()? ms[d]-'a': -1;

	for(int j = 0; j < K+1; j++) {
		int y = adj[x][j];
		if(!y) continue;

		if(j == K) pr('P'); else {
			if(!in || in && j != c) pr(j), dfs(y, 0, d+1);
		}
	}

	if(~c) pr(c), dfs(adj[x][c], 1, d+1);
	if(!in) pr('-');
}

int main() {
	fast_io;

	int n, l = 0; string s;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> s, add(s);
		if((int)s.size() > l) l = (int)s.size(), ms = s;
	}

	dfs(0, 1, 0);

	cout << (int)ret.size() << "\n";
	for(char c: ret) cout << c << "\n";
}

Compilation message

printer.cpp: In function 'void dfs(int, int, int)':
printer.cpp:38:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |    if(!in || in && j != c) pr(j), dfs(y, 0, d+1);
      |              ~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 600 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20392 KB Output is correct
2 Correct 62 ms 42148 KB Output is correct
3 Correct 30 ms 22004 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14576 KB Output is correct
2 Correct 74 ms 50952 KB Output is correct
3 Correct 45 ms 24816 KB Output is correct
4 Correct 62 ms 47120 KB Output is correct