Submission #157093

#	Time	Username	Problem	Language	Result	Execution time	Memory
157093		youngyojun	Type Printer (IOI08_printer)	C++11	100 / 100	236 ms	102128 KiB

printer

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define rb(x) ((x)&(-(x)))
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
 
const int MAXN = 25005;
 
struct NOD {
	NOD() {
		for(int i = 0; i < 26; i++)
			p[i] = NULL;
		mxd = 0;
		isE = isL = false;
	}
 
	NOD *p[26];
	int mxd;
	bool isE, isL;
};
 
vector<char> AnsV;
 
NOD *root;
 
int A[MAXN][25], AL[MAXN];
int N;
 
void dfs1(NOD *v) {
	int ret = 0;
	for(int i = 0; i < 26; i++) {
		if(NULL == v -> p[i]) continue;
		dfs1(v -> p[i]);
		upmax(ret, v -> p[i] -> mxd + 1);
	}
	v -> mxd = ret;
}
void dfs2(NOD *v) {
	v -> isL = true;
	for(int i = 0; i < 26; i++) {
		if(NULL == v -> p[i]) continue;
		if(v -> mxd != v -> p[i] -> mxd + 1) continue;
		dfs2(v -> p[i]);
		return;
	}
}
void dfs3(NOD *v) {
	if(v -> isE) AnsV.pb('P');
	for(int i = 0; i < 26; i++) {
		if(NULL == v -> p[i]) continue;
		if(v -> p[i] -> isL) continue;
		AnsV.pb('a' + i);
		dfs3(v -> p[i]);
		AnsV.pb('-');
	}
	for(int i = 0; i < 26; i++) {
		if(NULL == v -> p[i]) continue;
		if(!(v -> p[i] -> isL)) continue;
		AnsV.pb('a' + i);
		dfs3(v -> p[i]);
		return;
	}
}
 
int main() {
	scanf("%d", &N);
	for(int i = 0; i < N; i++) {
		char S[55];
		scanf(" %s", S);
		AL[i] = int(strlen(S));
		for(int j = 0; S[j]; j++)
			A[i][j] = S[j]-'a';
	}
 
	root = new NOD();
 
	for(int i = 0; i < N; i++) {
		NOD *v = root;
		for(int j = 0; j < AL[i]; j++) {
			int t = A[i][j];
			if(NULL == v -> p[t])
				v -> p[t] = new NOD();
			v = v -> p[t];
		}
		v -> isE = true;
	}
 
	dfs1(root);
	dfs2(root);
 
	dfs3(root);
 
	printf("%d\n", sz(AnsV));
	for(char v : AnsV) {
		putchar(v);
		putchar('\n');
	}
	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
printer.cpp:76: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