Submission #1313783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313783		algoproclub	Type Printer (IOI08_printer)	C++20	10 / 100	56 ms	25928 KiB

printer

// UUID: bb555bae-4995-4d74-9397-182057e8eebe
#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');
			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);
	cout << dfs(0)+n-maxLen;
	while(strans.back()=='-') strans.pop_back();
	for(char x : strans) cout << '\n' << x;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10