oj.uz

Submission #120072

# Submission time Handle Problem Language Result Execution time Memory
120072 2019-06-23T07:50:10 Z Boxworld Type Printer (IOI08_printer) C++14
60 / 100
 1000 ms 34524 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=500500;
struct TREE{int nxt[26];bool end,mk;}tree[N];
string s[N],m,ans="";
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(){
	cin>>n;
	memset(tree[0].nxt,-1,sizeof(tree[0].nxt));
	for (int i=0;i<n;i++){
		cin>>s[i];insert(s[i]);
		if(s[i].length()>m.length())m=s[i];
	}
	mark(m);
	dfs(root);
	cout<<S<<"\n"<<ans;
	return 0;
}

Compilation message

printer.cpp: In function 'void insert(std::__cxx11::string)':
printer.cpp:14: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:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<x.length();i++){
               ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct
2 Correct 17 ms 15980 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15972 KB Output is correct
2 Correct 16 ms 16000 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16128 KB Output is correct
2 Correct 19 ms 16512 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16896 KB Output is correct
2 Correct 35 ms 17184 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 19292 KB Output is correct
2 Execution timed out 1080 ms 22992 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 23988 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 1074 ms 34524 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 30584 KB Time limit exceeded
2 Halted 0 ms 0 KB -