oj.uz

Submission #951839

# Submission time Handle Problem Language Result Execution time Memory
951839 2024-03-22T19:47:10 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 110 ms 106584 KB 
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>

#define  DBG(x         ) cerr<<#x<<" = "<<(x)<<endl
#define DBG2(x, y      ) cerr<<#x<<" = "<<(x)<<", "<<#y<<" = "<<(y)<<endl
#define DBG3(x, y, z   ) cerr<<#x<<" = "<<(x)<<", "<<#y<<" = "<<(y)<<", "<<#z<<" = "<<(z)<<endl
#define DBG4(x, y, z, w) cerr<<#x<<" = "<<(x)<<", "<<#y<<" = "<<(y)<<", "<<#z<<" = "<<(z)<<", "<<#w<<" = "<<(w)<<endl
#define RAYA cerr<<" =============== "<<endl

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fort(i, n) for(int i = 0; i <= int(n); i++)
#define fori(i, a, n) for(int i = a; i < int(n); i++)
#define forit(i, a, n) for(int i = a; i <= int(n); i++)

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

using namespace std;

template<typename T>
ostream & operator<<(ostream &os, const vector<T> &v){
    os<<"[";
    forn(i, (int) v.size()){
        if(i) os<<", ";
        os<<v[i];
    }
    os<<"]";
    return os;
}

template<typename S, typename T>
ostream & operator<<(ostream &os, const pair<S, T> &p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int ALP = 26;

typedef struct Node *pnode;

struct Node{
	bool v = 0;
	pair<int, int> longest = {0, -1};
	pnode m[ALP];
	Node(){
		forn(i, ALP) m[i] = NULL;
	}
};

vector<char> res;

struct Trie{
	pnode root;
	Trie(){
		root = new Node();
	}
	void insert(const string &s){
		int n = s.size();
		pnode curr = root;
		for(int i = 0; i < n; i++){
			int idx = s[i] - 'a';
			curr->longest = max(curr->longest, {n-i, idx});
			if(!curr->m[idx]) curr->m[idx] = new Node();
			curr = curr->m[idx];
		}
		curr->v = 1;
	}
	void dfs(pnode curr, bool l){
		if(curr->v) res.push_back('P');
		forn(i, ALP){
			if(!curr->m[i]) continue;
			if(curr->longest.second==i && l) continue;
			res.push_back(char(i+'a'));
			dfs(curr->m[i], 0);
			res.push_back('-');
		}
		if(curr->longest.first && l){
			res.push_back(char(curr->longest.second+'a'));
			dfs(curr->m[curr->longest.second], 1);
		}
	}
	void dfs(){
		dfs(root, 1);
	}
};

void solve(){
	
	int n;
	cin>>n;
	
	Trie printer;
	while(n--){
		string s;
		cin>>s;
		printer.insert(s);
	}
	
	printer.dfs();
	
	cout<<res.size()<<"\n";
	for(char c : res) cout<<c<<"\n";

}

int main(){

	cin.tie(NULL);
	ios::sync_with_stdio(0);

    #ifdef LOCAL
        freopen("input.in", "r", stdin);
    #else
        //~ freopen("input.in", "r", stdin);
        //~ freopen("output.out", "w", stdout);
    #endif

    //~ int tcs;
    //~ cin>>tcs;
    //~ while(tcs--){
        solve();
    //~ }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6488 KB Output is correct
2 Correct 14 ms 13400 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15828 KB Output is correct
2 Correct 6 ms 3676 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 39104 KB Output is correct
2 Correct 94 ms 89540 KB Output is correct
3 Correct 49 ms 46284 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 30384 KB Output is correct
2 Correct 110 ms 106584 KB Output is correct
3 Correct 55 ms 52432 KB Output is correct
4 Correct 96 ms 100628 KB Output is correct