oj.uz

Submission #920477

# Submission time Handle Problem Language Result Execution time Memory
920477 2024-02-02T15:24:03 Z BBart888 Type Printer (IOI08_printer) C++14
100 / 100
 147 ms 91332 KB 
#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include <cstdlib>
#include <complex>
#include <array>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <random>
#define fileIO(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);}



using namespace std;
const int MAXN = 1e6 + 111;
using ll = long long;
const int P = 31;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
using ld = long double;
const ld EPS = 1e-5;
using pii = pair<int, int>;
typedef complex<ll> Point;
const int K = 600;


int n;
int trie[MAXN][27];
string str;
int node_cnt;
bool stop[MAXN];
int longest[MAXN];
vector<char> answer;

void add(const string & str)
{
	int curr_node = 0;
	for (int i = 0; i < str.size(); i++)
	{
		int nxt = str[i] - 'a';
		if (trie[curr_node][nxt] == 0)
			trie[curr_node][nxt] = ++node_cnt;
		curr_node = trie[curr_node][nxt];
	}
	stop[curr_node] = true;
}

vector<pair<int, int>> order[MAXN];

void dfs(int v)
{
	longest[v] = 1;

	for (int i = 0; i < 27; i++)
	{
		int nxt = trie[v][i];
		if (nxt > 0)
		{
			dfs(nxt);
			order[v].push_back({ longest[nxt],i });
			longest[v] = max(longest[v], longest[nxt] + 1);
		}
	}

	sort(order[v].begin(), order[v].end());
}

void print_it(int v)
{
	if (stop[v])
		answer.push_back('P');
	if (order[v].size() == 0)
	{
		answer.push_back('-');
		return;
	}
	for (int i = 0; i < order[v].size(); i++)
	{
		int nxt_char = order[v][i].second;
		int nxt_node = trie[v][nxt_char];
		answer.push_back((char)(nxt_char + 'a'));
		print_it(nxt_node);
	}
	answer.push_back('-');
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	//fileIO("cardgame");

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> str;
		add(str);
	}

	dfs(0);

	print_it(0);

	while (answer.back() == '-')
		answer.pop_back();

	cout << answer.size() << '\n';

	for (auto x : answer)
		cout << x << '\n';


	return 0;
}

Compilation message

printer.cpp: In function 'void add(const string&)':
printer.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < str.size(); i++)
      |                  ~~^~~~~~~~~~~~
printer.cpp: In function 'void print_it(int)':
printer.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for (int i = 0; i < order[v].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 7 ms 27224 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27228 KB Output is correct
2 Correct 7 ms 27272 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27224 KB Output is correct
2 Correct 7 ms 27228 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 27740 KB Output is correct
2 Correct 9 ms 27992 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 30296 KB Output is correct
2 Correct 20 ms 34396 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35800 KB Output is correct
2 Correct 12 ms 28760 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 49360 KB Output is correct
2 Correct 121 ms 81392 KB Output is correct
3 Correct 63 ms 53712 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 44108 KB Output is correct
2 Correct 147 ms 91332 KB Output is correct
3 Correct 79 ms 57324 KB Output is correct
4 Correct 104 ms 87924 KB Output is correct