oj.uz

Submission #105551

# Submission time Handle Problem Language Result Execution time Memory
105551 2019-04-13T12:30:09 Z wilwxk Type Printer (IOI08_printer) C++11
60 / 100
 1000 ms 263168 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=5e5+3;
int g[MAXN][30];
int dp[MAXN][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);

}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 59128 KB Output is correct
2 Correct 49 ms 59000 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 59004 KB Output is correct
2 Correct 48 ms 59000 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 59000 KB Output is correct
2 Correct 51 ms 58972 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 59000 KB Output is correct
2 Correct 49 ms 59044 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 59100 KB Output is correct
2 Correct 53 ms 59128 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 59128 KB Output is correct
2 Correct 59 ms 59180 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 59384 KB Output is correct
2 Execution timed out 1062 ms 172216 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 696 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 200040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 252896 KB Time limit exceeded
2 Halted 0 ms 0 KB -