POJ 3437 Tree Grafting

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define N 40005

int main(int argc, char *argv[])
{
    char s[N];
    int tree_depth;
    int father[N];
    int bi_depth[N];
    int left_child[N];
    int max_tree_depth, max_bi_depth;

    int num = 0;
    while (1) {
        ++num;
        scanf("%s", s);
        int len = strlen(s);
        if (s[0] == '#')
            break;

        tree_depth = 0;
        max_tree_depth = 0;
        max_bi_depth = 0;
        memset(father, 0, N * sizeof(int));
        memset(bi_depth, 0, N * sizeof(int));
        memset(left_child, 0, N * sizeof(int));

        for (int i = 1; i <= len; ++i) {
            if (s[i-1] == 'd') {
                ++tree_depth;
                if (max_tree_depth < tree_depth)
                    max_tree_depth = tree_depth;

                father[i] = i - 1;
                bi_depth[i] = bi_depth[i-1] + left_child[i-1] + 1;
                ++left_child[i-1];
                if (max_bi_depth < bi_depth[i])
                    max_bi_depth = bi_depth[i];
            }
            else if (s[i-1] == 'u') {
                --tree_depth;
                bi_depth[i] = bi_depth[father[i-1]];
                left_child[i] = left_child[father[i-1]];
                father[i] = father[father[i-1]];
            }
        }
        printf("Tree %d: %d => %d\n", num, max_tree_depth, max_bi_depth);
    }
    return 0;
}