oj.uz

Submission #53705

# Submission time Handle Problem Language Result Execution time Memory
53705 2018-07-01T05:06:48 Z 강한남자강한필(#2035) Type Printer (IOI08_printer) C++11
100 / 100
 143 ms 51216 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]);
			ans[tp++] = '-';
		}
	for(int i=arr[node].lastvisit+1; i<26; ++i)
		if(arr[node].next[i])
		{
			ans[tp++] = 'a' + i;
			traverse(arr[node].next[i]);
			ans[tp++] = '-';
		}
	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;
		return res;
	}
}

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);
	for(int i=0; i<tp-maxlength; ++i)
		printf("%c\n", ans[i]);
	return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
printer.cpp:78: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 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3392 KB Output is correct
2 Correct 20 ms 6720 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7872 KB Output is correct
2 Correct 19 ms 7872 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 19024 KB Output is correct
2 Correct 143 ms 43088 KB Output is correct
3 Correct 66 ms 43088 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 43088 KB Output is correct
2 Correct 140 ms 51216 KB Output is correct
3 Correct 78 ms 51216 KB Output is correct
4 Correct 125 ms 51216 KB Output is correct