oj.uz

Submission #120075

# Submission time Handle Problem Language Result Execution time Memory
120075 2019-06-23T07:58:50 Z Boxworld Type Printer (IOI08_printer) C++14
100 / 100
 122 ms 49656 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=500500;
struct TREE{int nxt[26];bool end,mk;}tree[N];
string s,m;
char ss[N],ans[N*2+1];
int S=0,T=0,n,root=0,fin=0;
int newnode(){
	T++;
	memset(tree[T].nxt,-1,sizeof(tree[T].nxt));
	return T;
}
void insert(string x){
	int cnr=root;
	for (int i=0;i<x.length();i++){
		int now=x[i]-'a'; 
		if (tree[cnr].nxt[now]==-1)tree[cnr].nxt[now]=newnode();
		cnr=tree[cnr].nxt[now];
	}
	tree[cnr].end=1;
}
void mark(string x){
	int cnr=root;
	for (int i=0;i<x.length();i++){
		int now=x[i]-'a';
		cnr=tree[cnr].nxt[now];
		tree[cnr].mk=1;
	}
}
void dfs(int cnr){
	if(tree[cnr].end==1)ans[S++]='P';
	int tmp=-1;
	for (int i=0;i<26;i++)
	if (tree[cnr].nxt[i]!=-1){
		int now=tree[cnr].nxt[i];
		if (tree[now].mk!=1){
			ans[S++]=char(i+'a');
			dfs(now);
		}
		else tmp=i;
	}
	if (tmp!=-1){
		ans[S++]=char(tmp+'a');
		dfs(tree[cnr].nxt[tmp]);
	}
	if (tmp==-1&&tree[cnr].mk)fin=1;
	if(!fin)ans[S++]='-';
}
int main(){
	scanf("%d",&n);
	memset(tree[0].nxt,-1,sizeof(tree[0].nxt));
	for (int i=0;i<n;i++){
		scanf("%s",ss);
		string s(ss);
		insert(s);
		if(s.length()>m.length())m=s;
	}
	mark(m);
	dfs(root);
	printf("%d\n",S);
	for (int i=0;i<S;i++)printf("%c\n",ans[i]);
	return 0;
}

Compilation message

printer.cpp: In function 'void insert(std::__cxx11::string)':
printer.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<x.length();i++){
               ~^~~~~~~~~~~
printer.cpp: In function 'void mark(std::__cxx11::string)':
printer.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<x.length();i++){
               ~^~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
printer.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",ss);
   ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3072 KB Output is correct
2 Correct 16 ms 6392 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7416 KB Output is correct
2 Correct 10 ms 1964 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 18220 KB Output is correct
2 Correct 105 ms 41848 KB Output is correct
3 Correct 55 ms 21752 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14200 KB Output is correct
2 Correct 122 ms 49656 KB Output is correct
3 Correct 65 ms 24568 KB Output is correct
4 Correct 98 ms 46840 KB Output is correct