oj.uz

Submission #734656

# Submission time Handle Problem Language Result Execution time Memory
734656 2023-05-02T18:32:45 Z Hydrolyzed Type Printer (IOI08_printer) C++14
0 / 100
 40 ms 36744 KB 
/*
 * AUTHOR	: Hydrolyzed~
 * SCHOOL	: RYW
 * TASK		: TYPE PRINTER
 * ALGO		: Trie
 * DATE		: 3 May 2023
 * */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#ifndef _DEBUG
// @==== Libary ====@ //

// @================@ //
#endif

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;

// @=== Debugger ===@ //
#ifdef _DEBUG
#include "debug.hpp"
#else
#define dbg(...) 0
#endif
// @================@ //

using ll = long long;

struct node_t{
	int cnt = 0;
	bool done;
	node_t *nxt[26];

	node_t(){
		cnt = 0;
		done = false;
		for(int i=0; i<26; ++i){
			nxt[i] = NULL;
		}
	}
};

struct trie_t{
	node_t root;
	void insert(string s){
		node_t *cur = &root;
		for(int i=0; i<(int)s.size(); ++i){
			if(cur->nxt[s[i] - 'a'] == NULL){
				cur->nxt[s[i] - 'a'] = new node_t();
			}
			cur = cur->nxt[s[i] - 'a'];
		}
		cur->cnt++;
	}
	void check(string s){
		node_t *cur = &root;
		for(int i=0; i<(int)s.size(); ++i){
			cur = cur->nxt[s[i] - 'a'];
			cur->done = true;
		}
	}
} t;

string answer_string;

int dfs(node_t *u){
	int res = u->cnt;
	for(int i=0; i<res; ++i){
		answer_string += "P\n";
	}
	for(int i=0; i<26; ++i){
		if(u->nxt[i] != NULL && u->nxt[i]->done == false){
			answer_string += ((char) (i + 'a'));
			answer_string += "\n";
			res += dfs(u->nxt[i]);
			answer_string += "-\n";
			res += 2;
		}
	}
	for(int i=0; i<26; ++i){
		if(u->nxt[i] != NULL && u->nxt[i]->done == true){
			answer_string += ((char) (i + 'a'));
			answer_string += "\n";
			res += dfs(u->nxt[i]);
			res += 1;
		}
	}
	return res;
}

inline void solution(){
	int n;
	string s, l = "";
	cin >> n;
	for(int i=1; i<=n; ++i){
		cin >> s;
		t.insert(s);
		if(s.size() > l.size()){
			l = s;
		}
	}	
	t.check(l);
	cout << dfs(&t.root) << "\n";
	cout << answer_string;
	return ;
}

signed main(){
	cin.tie(nullptr)->ios::sync_with_stdio(false);	
	int q = 1;
//	cin >> q;
	while(q--){
		solution();
		cout << "\n";
	}
	return 0;
}
// https://github.com/MasterIceZ/archive/tree/main/cpp-template

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1748 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5972 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 14812 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 36744 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 28676 KB Expected EOF
2 Halted 0 ms 0 KB -