oj.uz

Submission #226640

# Submission time Handle Problem Language Result Execution time Memory
226640 2020-04-24T16:17:59 Z tushar_2658 Type Printer (IOI08_printer) C++14
20 / 100
 748 ms 70284 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 25005;
string s[maxn];
int t[maxn * 20 * 26][26], cnt[maxn * 20 * 26];
int node = 0;
int par[maxn * 20 * 26];

void insert(string s){
	int mx = s.size();
	int cur = 0;
	for(auto c : s){
		if(!t[cur][c - 'a']){
			t[cur][c - 'a'] = ++node;
		}
		cnt[t[cur][c - 'a']] = max(cnt[t[cur][c - 'a']], mx);
		par[t[cur][c - 'a']] = cur;
		cur = t[cur][c - 'a'];
	}
}

vector<char> v;

void dfs(int cur){
	bool leaf = 1;
	for(int i = 0; i < 26; ++i){
		if(t[cur][i]){
			leaf = 0;
			break;
		}
	}
	if(leaf){
		v.push_back('P');
		int x = par[cur];
		int prv = cur;
		while(x != -1){
			vector<int> vv;
			for(int i = 0; i < 26; ++i){
				if(t[x][i]){
					vv.push_back(i);
				}
			}
			if(vv.size() == 1){
				v.push_back('-');
				t[x][vv[0]] = 0;
			}else {
				for(int i = 0; i < 26; ++i){
					if(t[x][i] == prv){
						v.push_back('-');
						t[x][i] = 0;
						break;
					}
				}
				break;
			}
			prv = x;
			x = par[x];
		}
		return;
	}
	vector<pair<int, pair<int, int>>> vv;
	for(int i = 0; i < 26; ++i){
		if(t[cur][i]){
			vv.push_back(make_pair(cnt[t[cur][i]], make_pair(t[cur][i], i)));
		}
	}
	sort(vv.begin(), vv.end());
	for(auto i : vv){
		v.push_back((char)(i.second.second + 'a'));
		dfs(i.second.first);
	}
}

int main(int argc, char const *argv[])
{
//	freopen("in.txt", "r", stdin);
	int n;
	cin >> n;
	memset(par, -1, sizeof par);
	for(int i = 0; i < n; ++i){
		cin >> s[i];
		insert(s[i]);
	}
	dfs(0);
	while(v.back() == '-')v.pop_back();
	cout << v.size() << endl;
	for(auto i : v){
		cout << i << endl;
	}

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 51960 KB Output is correct
2 Correct 29 ms 51968 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 51984 KB Output is correct
2 Correct 28 ms 52096 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 52096 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 51968 KB Output is correct
2 Incorrect 29 ms 51960 KB didn't print every word

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 52096 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 52892 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 54896 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 316 ms 59248 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 748 ms 70284 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 608 ms 66176 KB didn't print every word
2 Halted 0 ms 0 KB -