oj.uz

Submission #157093

# Submission time Handle Problem Language Result Execution time Memory
157093 2019-10-09T13:04:54 Z youngyojun Type Printer (IOI08_printer) C++11
100 / 100
 236 ms 102128 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 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6364 KB Output is correct
2 Correct 32 ms 13176 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15780 KB Output is correct
2 Correct 14 ms 4600 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 38564 KB Output is correct
2 Correct 203 ms 86052 KB Output is correct
3 Correct 106 ms 45552 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 31356 KB Output is correct
2 Correct 236 ms 102128 KB Output is correct
3 Correct 122 ms 51764 KB Output is correct
4 Correct 208 ms 96644 KB Output is correct