oj.uz

Submission #386811

# Submission time Handle Problem Language Result Execution time Memory
386811 2021-04-07T10:57:00 Z minoum Type Printer (IOI08_printer) C++17
20 / 100
 141 ms 148744 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 1e6+10, A = 30;
int t, c[MAXN][A], par[MAXN], h[MAXN], mx = 0, mxid = -1, n = 1;
vector <pair<int,int>> adj[MAXN];
bool mark[MAXN], isword[MAXN];
string ans = "";

inline void add(string s){
	int pt = 0, v = 0;
	while(pt < (int)s.size()){
		int ch = (s[pt]-'a');
		if(c[v][ch] == -1){
			par[n] = v; c[v][ch] = n; h[n] = h[v]+1;
			adj[v].push_back({n, ch}); n++;
		}
		v = c[v][ch];
		if(h[v] > mx) mx = h[v], mxid = v;
		pt++;
		if(pt == (int)s.size()) isword[v] = true;
	}
	return;
}

void dfs(int v, int parv){
	for(auto i: adj[v]){
		int u = i.first, ch = i.second;
		if(mark[u]) continue;
		ans += (char)('a'+ch);
		dfs(u, v);
	}
	for(auto i: adj[v]){
		int u = i.first, ch = i.second;
		if(!mark[u]) continue;
		ans += (char)('a'+ch);
		dfs(u, v);
	}
	if(isword[v]) ans += 'P';
	if(!mark[v]) ans += '-';
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for(int i = 0; i < MAXN; i++) 
		for(int j = 0; j < A; j++) c[i][j] = -1;
	cin >> t;
	par[0] = -1;
	for(int i = 0; i < t; i++){
		string s;
		cin >> s; add(s);
	}
	int v = mxid;
	while(v != -1){
		mark[v] = true; v = par[v];
	}
	dfs(0,-1);
	cout << (int)ans.size() << '\n';
	for(int i = 0; i < (int)ans.size(); i++) cout << ans[i] << '\n';
	return 0; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 141292 KB Output is correct
2 Correct 93 ms 141292 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 141292 KB Output is correct
2 Correct 94 ms 141312 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 141412 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 141292 KB Output is correct
2 Incorrect 92 ms 141292 KB printed invalid word

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 141292 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 141548 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 142444 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 144304 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 148744 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 146956 KB printed invalid word
2 Halted 0 ms 0 KB -