oj.uz

Submission #442024

# Submission time Handle Problem Language Result Execution time Memory
442024 2021-07-06T19:25:39 Z huukhang Type Printer (IOI08_printer) C++17
30 / 100
 54 ms 19140 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, vis;
};

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 = t[0].vis = 0;
	}

	void init(int u) {
		memset(t[u].child, -1, sizeof(t[u].child));
		t[u].fin = t[u].vis = 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 mark(const string &s, int val) {
		int p = 0;
		for (int i = 0; i < s.size(); ++i) {
			p = t[p].child[s[i] - 'a'];
			t[p].vis = val;
		}
	}

	void dfs(int u, int val, int nval = -1) {
		for (int i = 1; i <= t[u].fin; ++i) ans.pb('P');
		for (int i = 0; i < 26; ++i) {
			if (t[u].child[i] != -1 && t[t[u].child[i]].vis != val) {
				ans.pb(char(i + 'a'));
				dfs(t[u].child[i], val, nval);
				ans.pb('-');
			}
		}
		t[u].vis = nval;
	}
} t;

int n;
string mx;

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.mark(mx, 1);
	t.dfs(0, 1, 2);
	t.dfs(0, 2);
	while (ans.back() == '-') ans.pob();

	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:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~
printer.cpp: In member function 'void trie::mark(const string&, int)':
printer.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3276 KB Output is correct
2 Incorrect 18 ms 6620 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 7888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 19140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 15004 KB Output isn't correct
2 Halted 0 ms 0 KB -