oj.uz

Submission #226664

# Submission time Handle Problem Language Result Execution time Memory
226664 2020-04-24T17:20:46 Z tushar_2658 Type Printer (IOI08_printer) C++14
100 / 100
 163 ms 51692 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 1000000;
char s[25];
int t[maxn][26], ed[maxn], cnt[maxn];
int node = 0;
int par[maxn];

void insert(){
	int cur = 0;
	int sz = strlen(s);
	for(int i = 0; i < sz; ++i){
		int idx = s[i] - 'a';
		if(t[cur][idx] == 0){
			t[cur][idx] = ++node;
		}
		cur = t[cur][idx];
	}
	ed[cur] = 1;
}

vector<char> v;

void get(int cur){
	cnt[cur] = 1;
	for(int i = 0; i < 26; ++i){
		if(t[cur][i]){
			get(t[cur][i]);
			cnt[cur] = max(cnt[cur], cnt[t[cur][i]] + 1);
		}
	}
}

void dfs(int cur){
	if(ed[cur]){
		ed[cur] = 0;
		v.push_back('P');
	}
	vector<pair<int, int>> vv;
	int sz = 0;
	for(int i = 0; i < 26; ++i){
		if(t[cur][i]){
			vv.push_back(make_pair(cnt[t[cur][i]], i));
			sz++;
		}
	}
	sort(vv.begin(), vv.end());
	for(int i = 0; i < sz; ++i){
		v.push_back((char)(vv[i].second + 'a'));
		dfs(t[cur][vv[i].second]);
		v.push_back('-');
	}
}

int main(int argc, char const *argv[])
{
//	freopen("in.txt", "r", stdin);
	int n;
	cin >> n;
	for(int i = 0; i < n; ++i){
		scanf("%s", s); 
		insert();
	}
	get(0); 	
	dfs(0);
	int sz = v.size();
	while(v[sz - 1] == '-')--sz;
	printf("%d\n", sz);
	for(int i = 0; i < sz; ++i){
		printf("%c\n", v[i]);
	}

	return 0;
}

Compilation message

printer.cpp: In function 'int main(int, const char**)':
printer.cpp:62: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 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 7 ms 768 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1152 KB Output is correct
2 Correct 8 ms 1408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3328 KB Output is correct
2 Correct 25 ms 6780 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 19184 KB Output is correct
2 Correct 154 ms 43528 KB Output is correct
3 Correct 82 ms 22768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 15088 KB Output is correct
2 Correct 163 ms 51692 KB Output is correct
3 Correct 89 ms 25712 KB Output is correct
4 Correct 155 ms 48748 KB Output is correct