oj.uz

Submission #71497

# Submission time Handle Problem Language Result Execution time Memory
71497 2018-08-24T23:14:07 Z RezwanArefin01 Type Printer (IOI08_printer) C++17
100 / 100
 162 ms 63856 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 51192 KB Output is correct
2 Correct 47 ms 51328 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 51352 KB Output is correct
2 Correct 45 ms 51412 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 51412 KB Output is correct
2 Correct 45 ms 51468 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 51468 KB Output is correct
2 Correct 41 ms 51468 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 51500 KB Output is correct
2 Correct 42 ms 51500 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 51684 KB Output is correct
2 Correct 44 ms 51712 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 52256 KB Output is correct
2 Correct 59 ms 53040 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 53416 KB Output is correct
2 Correct 45 ms 53416 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 55916 KB Output is correct
2 Correct 152 ms 60788 KB Output is correct
3 Correct 102 ms 60788 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 60788 KB Output is correct
2 Correct 162 ms 63512 KB Output is correct
3 Correct 119 ms 63512 KB Output is correct
4 Correct 126 ms 63856 KB Output is correct