oj.uz

Submission #899341

# Submission time Handle Problem Language Result Execution time Memory
899341 2024-01-05T19:53:57 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 97 ms 60088 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');
		}
		
		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:96:15: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |   if(s.size() > mx){
      |      ~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
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 #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4048 KB Output is correct
2 Correct 13 ms 8908 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8652 KB Output is correct
2 Correct 7 ms 2640 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 30148 KB Output is correct
2 Correct 82 ms 60088 KB Output is correct
3 Correct 46 ms 29892 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15556 KB Output is correct
2 Correct 97 ms 59288 KB Output is correct
3 Correct 54 ms 31172 KB Output is correct
4 Correct 87 ms 59584 KB Output is correct