Submission #1313788

#TimeUsernameProblemLanguageResultExecution timeMemory
1313788algoproclubType Printer (IOI08_printer)C++20
10 / 100
55 ms25928 KiB
// UUID: 5b7c92eb-c845-4183-91b0-34458d19d646
#include <bits/stdc++.h>
using namespace std;

vector<char> nodes(1, 0);
vector<vector<int>> nbrs(1, vector<int>(0));
vector<bool> vis;
string strans;
int dfs(int Index){
	if(vis[Index]) return 0;
	vis[Index]=true;
	//printf("[%d: %d]", Index, nbrs[Index].size());
	int ans=0;
	for(int x : nbrs[Index]){
		if(x==-1){
			strans.push_back('P');
			ans++;
			continue;
		}
		if(!vis[x]){
			strans.push_back(nodes[x]);
			//printf("%c\n", nodes[x]);
			ans+=2+dfs(x);
			strans.push_back('-');
			//printf("-\n");
		}
	}
	return ans;
}

int main() {
	int n; cin >> n;
	int maxLen=0;
	vector<pair<int, string>> input(n); for(auto& x : input){
		cin >> x.second;
		x.first=x.second.size();
	}
	sort(input.begin(), input.end());
	for(int i=0;i<n;i++){
		const string& s=input[i].second;
		maxLen=max(maxLen, (int)s.size());
		int curr=0;
		for(char x : s){
			bool found=false;
			for(int y : nbrs[curr]){
				if(-1==y) continue;
				if(x==nodes[y]){
					found=true;
					curr=y;
					break;
				}
			}
			if(!found){
				nbrs[curr].push_back(nbrs.size());
				curr=nbrs.size();
				nbrs.push_back(vector<int>(0));
				nodes.push_back(x);
			}
		}
		nbrs[curr].push_back(-1);
	}
	vis.resize(nodes.size(), false);
	dfs(0);
	while(strans.back()=='-') strans.pop_back();
	cout << strans.size();
	for(char x : strans) cout << '\n' << x;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...