oj.uz

Submission #105558

# Submission time Handle Problem Language Result Execution time Memory
105558 2019-04-13T12:42:36 Z wilwxk Type Printer (IOI08_printer) C++11
100 / 100
 224 ms 74740 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 59 ms 68856 KB Output is correct
2 Correct 55 ms 68816 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 68860 KB Output is correct
2 Correct 66 ms 68868 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 68856 KB Output is correct
2 Correct 55 ms 68836 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 68840 KB Output is correct
2 Correct 65 ms 68860 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 68792 KB Output is correct
2 Correct 68 ms 68856 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 68856 KB Output is correct
2 Correct 62 ms 68984 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 69112 KB Output is correct
2 Correct 90 ms 69624 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 69804 KB Output is correct
2 Correct 72 ms 69240 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 70852 KB Output is correct
2 Correct 188 ms 74036 KB Output is correct
3 Correct 137 ms 71788 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 70616 KB Output is correct
2 Correct 224 ms 74740 KB Output is correct
3 Correct 138 ms 71956 KB Output is correct
4 Correct 185 ms 74348 KB Output is correct