oj.uz

Submission #53698

# Submission time Handle Problem Language Result Execution time Memory
53698 2018-07-01T04:56:46 Z 강한남자강한필(#2035) Type Printer (IOI08_printer) C++11
10 / 100
 143 ms 51220 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 25000;
const int MAXC = 20;
struct Node
{
	bool dest;
	int next[26];
	int lastvisit;
};

int used = 1;
Node arr[MAXN*MAXC+1];

int tp = 0;
char ans[2*MAXN*(MAXC+2)];

int root = 1;
int maxlength = 0;
void traverse(int node)
{
	//printf("%d %d %d\n", node, arr[node].dest, arr[node].lastvisit);
	if(arr[node].dest) ans[tp++] = 'P';
	for(int i=0; i<arr[node].lastvisit; ++i)
		if(arr[node].next[i])
		{
			ans[tp++] = 'a' + i;
			traverse(arr[node].next[i]);
		}
	for(int i=arr[node].lastvisit+1; i<26; ++i)
		if(arr[node].next[i])
		{
			ans[tp++] = 'a' + i;
			traverse(arr[node].next[i]);
		}
	if(arr[node].next[arr[node].lastvisit])
	{
		ans[tp++] = 'a'+arr[node].lastvisit;
		traverse(arr[node].next[arr[node].lastvisit]);
	}
	ans[tp++] = '-';
}

bool push(int node, char* buf, int depth)
{
	if(*buf == 0)
	{
		arr[node].dest = true;
		if(maxlength < depth)
		{
			maxlength = depth;
			return true;
		}
		return false;
	}
	else
	{
		int targ = (*buf) - 'a';
		//printf("%d\n", targ);
		if(arr[node].next[targ] == 0)
			arr[node].next[targ] = ++used;
		bool res = push(arr[node].next[targ], buf+1, depth+1);
		if(res) arr[node].lastvisit = targ;
	}
}

int main()
{
	int N;
	scanf("%d", &N);
	for(int i=0; i<N; ++i)
	{
		char buf[MAXC+1];
		scanf("%s", buf);
		push(root, buf, 0);
	}
	traverse(root);
	printf("%d\n",tp-maxlength-1);
	for(int i=0; i<tp-maxlength-1; ++i)
		printf("%c\n", ans[i]);
	return 0;
}

Compilation message

printer.cpp: In function 'bool push(int, char*, int)':
printer.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
printer.cpp: In function 'int main()':
printer.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
printer.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf);
   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 548 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 548 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 548 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 548 KB Output is correct
2 Incorrect 5 ms 912 KB didn't print every word

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1296 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3404 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 7868 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 19080 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 19080 KB Output is correct
2 Correct 143 ms 51220 KB Output is correct
3 Incorrect 97 ms 51220 KB didn't print every word
4 Halted 0 ms 0 KB -