oj.uz

Submission #53701

# Submission time Handle Problem Language Result Execution time Memory
53701 2018-07-01T04:57:35 Z 강한육군장홍준(#2037) Type Printer (IOI08_printer) C++11
100 / 100
 207 ms 51264 KB 
#include<stdio.h>
#include<string.h>
struct ND {
	int nxt[26], lp;
	bool is_ed;
}a[500001];
char ans[1212121], S[21];int an, sz;
int max(int a, int b) { if (a < b)return b; return a; }
void mk() {
	int now = 0, L = strlen(S);
	for (int i = 0; i < L; i++) {
		if (!a[now].nxt[S[i] - 'a'])a[now].nxt[S[i] - 'a'] = ++sz;
		now = a[now].nxt[S[i] - 'a'];
		a[now].lp = max(a[now].lp, L);
	}
	a[now].is_ed = 1;
}
void dfs(int now) {
	int mx = 0, mxw = -1;
	if (a[now].is_ed)ans[an++] = 'P';
	for (int i = 0; i < 26; i++)if (mx < a[a[now].nxt[i]].lp)mx = a[a[now].nxt[i]].lp, mxw = i;
	for (int i = 0; i < 26; i++)if (a[now].nxt[i]) {
		if (i == mxw)continue;
		ans[an++] = 'a' + i;
		dfs(a[now].nxt[i]);
	}
	if (mxw != -1) {
		ans[an++] = 'a' + mxw;
		dfs(a[now].nxt[mxw]);
	}
	ans[an++] = '-';
}
int main() {
	int n, i; scanf("%d", &n);
	for (i = 0; i < n; i++)scanf("%s", S), mk();
	dfs(0);
	while (ans[an - 1] == '-')an--;
	printf("%d\n", an);
	for (i = 0; i < an; i++)printf("%c\n", ans[i]);
	return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:34:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, i; scanf("%d", &n);
            ~~~~~^~~~~~~~~~
printer.cpp:35:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n; i++)scanf("%s", S), mk();
                         ~~~~~~~~~~~~~~^~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3404 KB Output is correct
2 Correct 28 ms 6748 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7900 KB Output is correct
2 Correct 12 ms 7900 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 19100 KB Output is correct
2 Correct 159 ms 43276 KB Output is correct
3 Correct 93 ms 43276 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 43276 KB Output is correct
2 Correct 207 ms 51264 KB Output is correct
3 Correct 101 ms 51264 KB Output is correct
4 Correct 180 ms 51264 KB Output is correct