oj.uz

Submission #386815

# Submission time Handle Problem Language Result Execution time Memory
386815 2021-04-07T11:06:16 Z minoum Type Printer (IOI08_printer) C++17
100 / 100
 217 ms 161576 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){
	if(isword[v]) ans += 'P';
	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(!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 93 ms 141292 KB Output is correct
2 Correct 92 ms 141292 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 141276 KB Output is correct
2 Correct 95 ms 141248 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 141420 KB Output is correct
2 Correct 95 ms 141468 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 141548 KB Output is correct
2 Correct 95 ms 141676 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 142444 KB Output is correct
2 Correct 108 ms 143852 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 144124 KB Output is correct
2 Correct 100 ms 142188 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 148488 KB Output is correct
2 Correct 194 ms 158248 KB Output is correct
3 Correct 144 ms 150156 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 146700 KB Output is correct
2 Correct 217 ms 161576 KB Output is correct
3 Correct 153 ms 151304 KB Output is correct
4 Correct 190 ms 160420 KB Output is correct