oj.uz

답안 #442330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442330 2021-07-07T13:09:51 Z huukhang Type Printer (IOI08_printer) C++11
100 / 100
 128 ms 49852 KB 
/*
						   Khangnh's code

“You can either experience the pain of discipline or the pain of regret. 
						The choice is yours.”
*/

// - Only when necessary :d
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,fma")

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

#define fileopen(a, b) freopen(((string)a + ".inp").c_str(), "r", stdin); freopen(((string)b + ".out").c_str(), "w", stdout);

#define ll long long
// #define int long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
typedef pair<int, int> pii;

const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const double eps = 1e-9;

struct node {
	int child[26];
	int fin;
};

string mx;
vector<char> ans;
struct trie {
	int n;
	node t[500005];

	trie() : n(0) {
		memset(t[0].child, -1, sizeof(t[0].child));
		t[0].fin = 0;
	}

	void init(int u) {
		memset(t[u].child, -1, sizeof(t[u].child));
		t[u].fin = 0;
	}

	void push(string &s) {
		int p = 0;
		for (int i = 0; i < s.size(); ++i) {
			if (t[p].child[s[i] - 'a'] == -1) {
				init(++n);
				t[p].child[s[i] - 'a'] = n;
			}
			p = t[p].child[s[i] - 'a'];
		}
		++t[p].fin;
	}

	void dfs(int u, int dep, bool longest) {
		if (t[u].fin > 0) ans.pb('P');

		int c = mx[dep] - 'a';
		for (int i = 0; i < 26; ++i) {
			if (i == c && longest) continue;
			if (t[u].child[i] != -1) {
				ans.pb(char(i + 'a'));
				dfs(t[u].child[i], dep + 1, 0);
				ans.pb('-');
			}
		}

		if (dep < mx.size() && longest) {
			ans.pb(char(c + 'a'));
			if (t[u].child[c] != -1) dfs(t[u].child[c], dep + 1, 1);
		}
	}
} t;

int n;

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		string s;
		cin >> s;

		t.push(s);
		if (mx.size() < s.size()) mx = s;
	}

	t.dfs(0, 0, 1);

	cout << ans.size() << "\n";
	for (auto x : ans) cout << x << "\n";
}

signed main() {
	#ifdef LOCAL
		fileopen("input", "output");
		auto start = clock();
	#endif
	#ifndef LOCAL
//		fileopen("LAH", "LAH");
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int test = 1;
//	cin >> test;
	for (int tc = 1; tc <= test; ++tc) solve();
	#ifdef LOCAL
		auto end = clock();
		cout << "\n\nExecution time : " << double(end - start)/CLOCKS_PER_SEC << "[s]";
	#endif
	return 0;
}

Compilation message

printer.cpp: In member function 'void trie::push(std::string&)':
printer.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~
printer.cpp: In member function 'void trie::dfs(int, int, bool)':
printer.cpp:79:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   if (dep < mx.size() && longest) {
      |       ~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 716 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 3 ms 1228 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3148 KB Output is correct
2 Correct 16 ms 6476 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 7624 KB Output is correct
2 Correct 7 ms 1880 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 18436 KB Output is correct
2 Correct 106 ms 41920 KB Output is correct
3 Correct 60 ms 21956 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 14568 KB Output is correct
2 Correct 128 ms 49852 KB Output is correct
3 Correct 69 ms 24780 KB Output is correct
4 Correct 117 ms 47136 KB Output is correct