Submission #71497

#	Time	Username	Problem	Language	Result	Execution time	Memory
71497		RezwanArefin01	Type Printer (IOI08_printer)	C++17	100 / 100	162 ms	63856 KiB

printer

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

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 5e5 + 10; 
int trie[N][26], idx, d[N], 
	ed[N], h[N], c[N]; 
char s[N]; 

void insert() {
	int cur = 0; 
	int len = strlen(s); 
	for(int i = 0; i < len; i++) {
		int &at = trie[cur][s[i] - 'a'];
		if(at == -1) at = ++idx; 
		cur = at; 
	} ed[cur] = 1;
}

void dfs(int u) {
	d[u] = 0;
	for(int i = 0; i < 26; i++) {
		int v = trie[u][i]; 
		if(v == -1) continue; 
		dfs(v);
		if(d[v] + 1 > d[u]) {
			d[u] = d[v] + 1; 
			h[u] = v; 
			c[u] = i; 
		}
	}
}
vector<char> ans; 
void print(int u) {
	if(ed[u]) ans.push_back('P'); 
	for(int i = 0; i < 26; i++) {
		int v = trie[u][i];
		if(v == -1 || v == h[u]) continue;
		ans.push_back(char('a' + i));
		print(v); 
	} 
	if(h[u]) {
		ans.push_back(char('a' + c[u]));
		print(h[u]);
	}
	ans.push_back('-');
}
int main(int argc, char const *argv[]) {
	int n; scanf("%d", &n);
	memset(trie, -1, sizeof trie); 
	for(int i = 0; i < n; i++) {
		scanf(" %s", s); 
		insert(); 
	}
	dfs(0); print(0); 

	while(ans.size() && ans.back() == '-') 
		ans.pop_back();

	printf("%d\n", (int)ans.size());
	for(char c : ans) putchar(c), putchar('\n');
}

Compilation message (stderr)

printer.cpp: In function 'int main(int, const char**)':
printer.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
printer.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", s); 
   ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10