oj.uz

Submission #846951

# Submission time Handle Problem Language Result Execution time Memory
846951 2023-09-08T18:13:35 Z Ivo_12 Type Printer (IOI08_printer) C++17
100 / 100
 171 ms 174336 KB 
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

struct TrieNode {
	int edgs[26];
	bool isend;
	pair < int, int > maxlen[26];
	TrieNode() {
		for(int i = 0; i < 26; i++) {
			edgs[i] = -1;
			maxlen[i].f = 0;
			maxlen[i].s = i;
		}
		isend = 0;
	}
};

TrieNode nodes[550010];
int cur = 1;
string s;
int n;
char abc[26];
char prnt[1550010];

void add( string s ) {
	int slen = (int) s.size();
	int curpos = 0;
	for(int i = 0; i < slen; i++) {
		if(nodes[curpos].edgs[s[i]-'a']==-1) {
			nodes[curpos].edgs[s[i]-'a'] = cur;
			cur++;
		}
		nodes[curpos].maxlen[s[i]-'a'].f=max(nodes[curpos].maxlen[s[i]-'a'].f, slen);
		curpos = nodes[curpos].edgs[s[i]-'a'];
	}
	nodes[curpos].isend = 1;
}

void out( int curpos ) {
	sort(nodes[curpos].maxlen, nodes[curpos].maxlen+26);
	if(nodes[curpos].isend) {
		prnt[cur] = 'P';
		cur++;
	}
	for(int i = 0; i < 26; i++) {
		if(nodes[curpos].maxlen[i].f!=0) {
			prnt[cur] = abc[nodes[curpos].maxlen[i].s];
			cur++;
			out(nodes[curpos].edgs[nodes[curpos].maxlen[i].s]);
			prnt[cur] = '-';
			cur++;
		}
	}
}

int main( void ) {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> s;
		add(s);
	}
	abc[0] = 'a';
	for(int i = 1; i < 26; i++) abc[i] = abc[i-1]+1;
//	for(int i = 0; i < 26; i++) cout << nodes[0].maxlen[i].f << "\n";
	cur=0;
	out(0);
	cur-=nodes[0].maxlen[25].f;
	cout << cur << "\n";
	for(int i = 0; i < cur; i++) cout << prnt[i] << "\n";
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 171600 KB Output is correct
2 Correct 34 ms 171600 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 171844 KB Output is correct
2 Correct 33 ms 171600 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 171600 KB Output is correct
2 Correct 34 ms 171856 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 171856 KB Output is correct
2 Correct 35 ms 171864 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 171856 KB Output is correct
2 Correct 48 ms 172112 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 172260 KB Output is correct
2 Correct 41 ms 172112 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 172880 KB Output is correct
2 Correct 140 ms 173900 KB Output is correct
3 Correct 88 ms 173240 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 172624 KB Output is correct
2 Correct 171 ms 174336 KB Output is correct
3 Correct 96 ms 173376 KB Output is correct
4 Correct 157 ms 174160 KB Output is correct