oj.uz

Submission #734643

# Submission time Handle Problem Language Result Execution time Memory
734643 2023-05-02T18:18:52 Z vjudge1 Type Printer (IOI08_printer) C++11
0 / 100
 37 ms 36996 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(auto x: s){
			if(cur->nxt[x - 'a'] == NULL){
				cur->nxt[x - 'a'] = new node_t();
			}
			cur = cur->nxt[x - 'a'];
		}
		cur->cnt++;
	}
	void check(string s){
		node_t *cur = &root;
		for(auto x: s){
			cur = cur->nxt[x - '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){
			continue;
		}
		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 == false){
			continue;
		}
		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 1 ms 212 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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