oj.uz

Submission #385456

# Submission time Handle Problem Language Result Execution time Memory
385456 2021-04-04T10:58:07 Z negar_a Type Printer (IOI08_printer) C++14
100 / 100
 241 ms 78308 KB 
//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 25e3 * 20 + 5;
int mat[maxn][26], h[maxn], mh[maxn], x[maxn];
vector <pair <int, char>> adj[maxn];
vector <char> ans;

int cnt = 1;
void add(string s, int v, int h){
	if(h == (int)s.size()){
		x[v] ++;
		return;
	}
	if(!mat[v][s[h] - 'a']){
		mat[v][s[h] - 'a'] = cnt;
		adj[v].pb({cnt, s[h]});
		cnt ++;
	}
	add(s, mat[v][s[h] - 'a'], h + 1);
}

bool cmp(pair <int, char> a, pair <int, char> b){
	return mh[a.F] < mh[b.F];
}

void dfs(int v){
	sort(adj[v].begin(), adj[v].end(), cmp);
	for(int i = 0; i < x[v]; i ++){
		ans.pb('P');
	}
	for(auto p : adj[v]){
		int u = p.F;
		ans.pb(p.S);
		dfs(u); 
	}
	ans.pb('-');
}
void dfs1(int v){
	mh[v] = h[v];
	for(auto p : adj[v]){
		int u = p.F;
		h[u] = h[v] + 1;
		dfs1(u); 
		mh[v] = max(mh[v], mh[u]);
	}
}

int main(){
	fast_io;
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++){
		string s;
		cin >> s;
		add(s, 0, 0);
	}
	dfs1(0);
	dfs(0);
	while(ans.back() == '-'){
		ans.pop_back();
	}
	cout << ans.size() << '\n';
	for(char u : ans){
		cout << u << '\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 12 ms 12652 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13164 KB Output is correct
2 Correct 13 ms 13420 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15852 KB Output is correct
2 Correct 33 ms 20332 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 21644 KB Output is correct
2 Correct 22 ms 14316 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 36076 KB Output is correct
2 Correct 197 ms 67688 KB Output is correct
3 Correct 116 ms 40684 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 30564 KB Output is correct
2 Correct 241 ms 78308 KB Output is correct
3 Correct 151 ms 44516 KB Output is correct
4 Correct 179 ms 74592 KB Output is correct