oj.uz

Submission #120073

# Submission time Handle Problem Language Result Execution time Memory
120073 2019-06-23T07:54:31 Z Boxworld Type Printer (IOI08_printer) C++14
60 / 100
 1000 ms 19644 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,ans="";
char ss[N];
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+="P\n",S++;
	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=ans+char(i+'a')+"\n";S++;
			dfs(now);
		}
		else tmp=i;
	}
	if (tmp!=-1){
		ans=ans+char(tmp+'a')+"\n";S++;
		dfs(tree[cnr].nxt[tmp]);
	}
	if (tmp==-1&&tree[cnr].mk)fin=1;
	if(!fin)ans+="-\n",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);
	cout<<S<<"\n"<<ans;
	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 5 ms 768 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1280 KB Output is correct
2 Correct 21 ms 1608 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 3696 KB Output is correct
2 Execution timed out 1081 ms 7076 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 8116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 19644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 14712 KB Time limit exceeded
2 Halted 0 ms 0 KB -