Submission #63222

#	Time	Username	Problem	Language	Result	Execution time	Memory
63222		nvmdava	Type Printer (IOI08_printer)	C++17	100 / 100	390 ms	86308 KiB

printer

#include<bits/stdc++.h>
using namespace std;

struct Node{
	char val;
	int in[26];
	vector<Node*> let;
	int lon, size;
	bool word;
	
	Node(){
		memset(in, 0, sizeof(in));
		lon = 0;
		size = 2;
		word = 0;
	}
	
	bool operator<(const Node *rhs) const{
		lon < (rhs -> lon);
	}
	
} *root;


bool cmp( Node *a, Node *b ){
	return a -> lon < b -> lon;
}

void sorter(Node *now){
	
	if( now -> let.size() == 0){
		return;
	}
	for(auto x : now -> let){
		sorter( x );
		now -> size += x -> size;
	}
	
	sort(now -> let.begin(), now -> let.end(), cmp);
	now -> lon = (now -> let.back() -> lon) + 1;
}

void insert(string s, Node* now, int i, int len){
	if(i == len){
		now -> word = 1;
		return;
	}
	if(now -> in[s[i] - 'a'] == 0){
		now -> let.push_back(new Node());
		now -> in[s[i] - 'a'] = now -> let.size();
	}
	now = now -> let[now -> in[s[i] - 'a'] - 1];
	now -> val = s[i];
	insert(s, now, i + 1, len);
}

int n;
void print(Node* now){
	
	if(now != root)cout<<now -> val<<'\n';
	if(now -> let.size() == 0){
		cout<<"P\n";
		n--;
		if(n == 0){
			exit(0);
		}
	} else {
		if(now -> word == 1){
			cout<<"P\n";
			n--;
			if(n == 0){
				exit(0);
			}
		}
		for(auto x : now -> let){
			print(x);
		}
	}
	cout<<"-\n";
}

int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int i;
	
	root = new Node();
	
	cin>>n;
	string s;
	for(i = 1; i <= n; i++){
		cin>>s;
		insert(s, root, 0, s.size());
	}
	sorter( root );
	int ans = root -> size + n - root -> lon - 2;
	cout<<ans<<"\n";
	print(root);
}

Compilation message (stderr)

printer.cpp: In member function 'bool Node::operator<(const Node*) const':
printer.cpp:19:7: warning: statement has no effect [-Wunused-value]
   lon < (rhs -> lon);
   ~~~~^~~~~~~~~~~~~~
printer.cpp:20:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^

• 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