记录编号	449954	评测结果	AAAAAAAAAA
题目名称	mk去撸串	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.147 s
提交时间	2017-09-15 16:05:02	内存使用	0.36 MiB

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

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

inline void read(char *s) { 
    register char *p = s;
    while(!islower(*p = getc()));
    while(islower(*(++p) = getc()));
    *p = '\0'; 
    return ;
}

typedef unsigned long long ULL;

struct NODE{ 
    ULL val;
    int fix, cnt;
    NODE *ls, *rs;

    NODE(ULL k) { 
        fix = rand();
        val = k, cnt = 1;
        ls = rs = NULL;
    }
};

inline ULL hash(char *str);
void Insert(NODE *&node, ULL k);
inline void Right(NODE *&k2);
inline void Left(NODE *&k2);
int dfs(NODE *node);

NODE *root;
char s[110];
unsigned len;
int N;

int Main() { 
#ifndef LOCAL
    freopen("string_.in", "r", stdin);
    freopen("string_.out", "w", stdout);
#endif
    N = read();
    int srand_seed;
    srand((long long)&srand_seed);
    for(int i = 0; i < N; ++i) { 
        read(s);
        Insert(root, hash(s));
    }
    printf("%d", dfs(root));
}
int Main_ = Main();
int main() { ;}

void Insert(NODE *&node, ULL k) { 
    if(!node) node = new NODE(k);
    else if(k < node->val) { 
        Insert(node->ls, k);
        if(node->ls->fix < node->fix) Right(node);
    } else if(node->val < k) { 
        Insert(node->rs, k);
        if(node->rs->fix < node->fix) Left(node);
    } else ++node->cnt;
    return ;
}

inline void Right(NODE *&k2) { 
    register NODE *k1 = k2->ls;
    k2->ls = k1->rs;
    k1->rs = k2; 
    k2 = k1;
    return ;
}

inline void Left(NODE *&k2) { 
    register NODE *k1 = k2->rs;
    k2->rs = k1->ls;
    k1->ls = k2; 
    k2 = k1;
    return ;
}

int dfs(NODE *node) { 
    if(!node) return 0;
    return max(max(dfs(node->ls), dfs(node->rs)), node->cnt);
}

inline ULL hash(char *str) { 
    static int seed = rand() % 1000;
    register ULL hs = 0;
    while(*str)
        hs = hs * seed + *str++;
    return hs;
}