Submission #105558

#	Time	Username	Problem	Language	Result	Execution time	Memory
105558		wilwxk	Type Printer (IOI08_printer)	C++11	100 / 100	224 ms	74740 KiB

printer

#include <bits/stdc++.h>
using namespace std;

const int MAXN=5e5+3;
int g[MAXN][35];
bool especial[MAXN];
int ruim[MAXN];
char letra[MAXN];
char c[35];
int n, contv=0;
vector<char> resp;

int novo(char c) { letra[++contv]=c; return contv; }

int predfs(int cur, int p) {
	int melhor=0; int cara=-1;
	for(int i=0; i<30; i++) {
		int viz=g[cur][i];
		if(viz==-1) continue;
		int val=predfs(viz, cur);
		if(val>melhor) melhor=val, cara=viz; 
	}
	ruim[cur]=cara;
	return melhor+1;
}

void dfs(int cur, int p, int k) {
	// printf("%d > %d\n", cur, ruim[cur]);
	if(cur!=0) resp.push_back(letra[cur]);
	if(especial[cur]) resp.push_back('P');
	for(int i=0; i<30; i++) {
		int viz=g[cur][i];
		if(viz==-1) continue;
		if(viz==ruim[cur]) continue;
		dfs(viz, cur, 1);
	}
	if(ruim[cur]!=-1) dfs(ruim[cur], cur, k);
	if(k) resp.push_back('-');
}

int main() {
	memset(g, -1, sizeof(g));

    scanf("%d", &n);
    for(int iii=1; iii<=n; iii++) {
    	scanf(" %s", c);
    	int m=strlen(c);
		int cur=0;
		for(int i=0; i<m; i++) {
			if(g[cur][c[i]-'a']==-1) g[cur][c[i]-'a']=novo(c[i]);
			cur=g[cur][c[i]-'a'];
		}
		especial[cur]=1;
    }

    predfs(0, 0);
    dfs(0, 0, 0);

    printf("%d\n", resp.size());
    for(auto cur : resp) printf("%c\n", cur);

}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:59:31: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", resp.size());
                    ~~~~~~~~~~~^
printer.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
printer.cpp:46:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf(" %s", c);
      ~~~~~^~~~~~~~~~

• 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