oj.uz

Submission #53709

# Submission time Handle Problem Language Result Execution time Memory
53709 2018-07-01T05:26:56 Z 윤교준(#1438) Type Printer (IOI08_printer) C++11
100 / 100
 242 ms 102056 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 432 KB Output is correct
2 Correct 2 ms 508 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 3 ms 620 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 748 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 756 KB Output is correct
2 Correct 3 ms 1404 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6556 KB Output is correct
2 Correct 28 ms 13472 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 38768 KB Output is correct
2 Correct 191 ms 85772 KB Output is correct
3 Correct 103 ms 85772 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 85772 KB Output is correct
2 Correct 242 ms 102056 KB Output is correct
3 Correct 125 ms 102056 KB Output is correct
4 Correct 184 ms 102056 KB Output is correct