제출 #105552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105552		wilwxk	Type Printer (IOI08_printer)	C++11	60 / 100	13 ms	6528 KiB

printer

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

const int MAXN=5e4+3;
int g[25003][30];
int dp[25003][2];
short especial[MAXN];
short ruim[MAXN];
char letra[MAXN];
int n, contv=0;
vector<char> resp;

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

void adiciona(char 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]-'a');
		cur=g[cur][c[i]-'a'];
	}
	especial[cur]=1;
	// printf("c %d\n", cur);
}

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]+'a');
	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 i=1; i<=n; i++) {
    	char c[30];
    	scanf(" %s", c);
    	adiciona(c);
    }

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

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

}

컴파일 시 표준 에러 (stderr) 메시지

printer.cpp: In function 'int main()':
printer.cpp:65: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:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
printer.cpp:58: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: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10