Submission #899341

#	Time	Username	Problem	Language	Result	Execution time	Memory
899341		vjudge1	Type Printer (IOI08_printer)	C++17	100 / 100	97 ms	60088 KiB

printer

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10