Submission #1313801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313801		algoproclub	Type Printer (IOI08_printer)	C++20	100 / 100	81 ms	30608 KiB

printer

// UUID: 9e0595c2-6fca-494a-b863-dd7a3486f7d0
#include <bits/stdc++.h>
using namespace std;

vector<char> nodes(1, 0);
vector<vector<array<int, 2>>> nbrs(1, vector<array<int, 2>>(0));
vector<bool> vis;
string strans;

int depthGen(int Index){
	if(vis[Index]) return 0;
	vis[Index]=true;
	int ans=0;
	for(auto& x : nbrs[Index]){
		if(x[1]==-1){
			continue;
		}
		if(!vis[x[1]]){
			ans=max(ans, (x[0]=1+depthGen(x[1])));
		}
	}
	sort(nbrs[Index].begin(), nbrs[Index].end());
	return ans;
}

void dfs(int Index){
	if(vis[Index]) return;
	vis[Index]=true;
	//printf("[%d: %d]", Index, nbrs[Index].size());
	for(auto [_, x] : nbrs[Index]){
		if(x==-1){
			strans.push_back('P');
			continue;
		}
		if(!vis[x]){
			strans.push_back(nodes[x]);
			dfs(x);
			//printf("%c\n", nodes[x]);
			strans.push_back('-');
			//printf("-\n");
		}
	}
}

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(auto [_, y] : nbrs[curr]){
				if(-1==y) continue;
				if(x==nodes[y]){
					found=true;
					curr=y;
					break;
				}
			}
			if(!found){
				nbrs[curr].push_back({0, nbrs.size()});
				curr=nbrs.size();
				nbrs.push_back(vector<array<int, 2>>(0));
				nodes.push_back(x);
			}
		}
		nbrs[curr].push_back({0, -1});
	}
	vis.resize(nodes.size(), false);
	depthGen(0);
	vis.assign(nodes.size(), false);
	dfs(0);
	while(strans.back()=='-') strans.pop_back();
	cout << strans.size();
	for(char x : strans) cout << '\n' << x;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:68:67: warning: narrowing conversion of 'nbrs.std::vector<std::vector<std::array<int, 2> > >::size()' from 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   68 |                                 nbrs[curr].push_back({0, nbrs.size()});
      |                                                          ~~~~~~~~~^~

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