oj.uz

Submission #899325

# Submission time Handle Problem Language Result Execution time Memory
899325 2024-01-05T19:24:33 Z vjudge1 Type Printer (IOI08_printer) C++17
20 / 100
 17 ms 30400 KB 
#include<bits/stdc++.h>

using namespace std;

struct node{
	array<int,26>nxt;
	bool term;
	int lon;
	
	node(){
		for(int i=0;i<26;i++){
			nxt[i] = 0;
		}
		term = false;
	}
};

vector<char>ans;

struct trie{
	vector<node>t;
	int n;
	trie(){
		t.resize(1);
		n = 1;
	}
	
	void add(string &s,bool es){
		int cur = 0;
		for(char c:s){
			if(!t[cur].nxt[c - 'a']){
				t.push_back(node());
				t[cur].nxt[c - 'a'] = n;
				n++;
			}
			cur = t[cur].nxt[c - 'a'];
			t[cur].lon = es;
		}
		
		t[cur].term = true;
		t[cur].lon = es;
	}
	
	bool find(string &s){
		int cur = 0;
		for(char c:s){
			cur = t[cur].nxt[c - 'a'];
			if(!cur) return false;
		}
		return t[cur].term;
	}
	
	void dfs(int v){
		if(t[v].term){
			ans.push_back('P');
			return;
		}
		
		int longer = -1;
		
		for(int i=0;i<26;i++){
			if(t[v].nxt[i]){
				int next = t[v].nxt[i];
				
				if(t[next].lon){
					longer = i;
					continue;
				}
				ans.push_back(char(i+'a'));
				dfs(next);
				ans.push_back('-');
			}
		}
		
		if(longer != -1){
			ans.push_back(char(longer + 'a'));
			dfs(t[v].nxt[longer]);
		}
	}
	
};

int main(){
	int n;
	cin>>n;
	
	trie t;
	
	string longer;
	int mx = 0;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		
		t.add(s,false);
		
		if(s.size() > mx){
			mx = s.size();
			longer = s;
		}
	}
	
	t.add(longer,true);
	
	t.dfs(0);
	cout<<ans.size()<<"\n";
	for(auto a:ans){
		cout<<a<<"\n";
	}
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:97:15: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   if(s.size() > mx){
      |      ~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1304 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 3 ms 4816 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 8 ms 8396 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 17 ms 30400 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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