ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1542. Автодополнение

RE test#11
Послано zhuchenxi 15 июл 2013 18:32
why??

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<climits>
#include<string>
#include<string.h>
#include<vector>
#define sf scanf
#define pf printf
#define cls(a) memset(a,0,sizeof(a))
#define _cls(a) memset(a,-1,sizeof(a))

using namespace std;

struct Edge_t{
    int to,next;
}edge[400000];
int hed[200000];
int et;


struct tree{
    tree *br[26];
    vector<int>vec;
    tree(){
        for(int i=0;i<26;++i) br[i]=NULL;
        vec.clear();
    }
};

struct Input{
    char str[18];
    int val;
}inp[100010];
tree *head;

inline void adde(int u,int v){
    edge[et].to=v,edge[et].next=hed[u],hed[u]=et++;
}

inline void addtree(char *st,int index){
    int id,i;
    tree *s=head;
    for(i=0;st[i];++i){
        id=st[i]-'a';
        if(!s->br[id])
            s->br[id]=new tree;
        s=s->br[id];
    }
    s->vec.push_back(index);
}
inline bool cmp(int a,int b){
    if(inp[a].val==inp[b].val) return strcmp(inp[a].str,inp[b].str)<0;
    return inp[a].val>inp[b].val;
}

void DEL(tree *s){
    int i;
    for(i=0;i<26;++i)
        if(s->br[i]) DEL(s->br[i]);
    s->vec.clear();
    delete(s);
}
int res[1000010];


void deal(char *st,int index){
    int i,id,j;
    tree *s=head;
    for(i=0;st[i];++i){
        id=st[i]-'a';
        if(!s->br[id]) return;
        s=s->br[id];
        for(j=0;j<s->vec.size();++j)
            adde(s->vec[j],index);
    }
}

int main(){
    int i,j;
    int n,m,sk;
    char str[18];
    while(scanf("%d",&n)!=EOF){
        head=new tree;
        _cls(hed);
        for(i=et=0;i<n;++i)
            sf("%s%d",inp[i].str,&inp[i].val);
        sf("%d",&m);
        for(j=0;j<m;++j){
            sf("%s",str);
            addtree(str,j);
        }
        for(i=0;i<n;++i)
            deal(inp[i].str,i);
        int e;
        for(i=0;i<m;++i){
            if(i) puts("");
            for(sk=0,e=hed[i];e!=-1;e=edge[e].next)
                res[sk++]=edge[e].to;
            if(!sk) continue;
            sort(res,res+sk,cmp);
            //if(sk>0)
            for(j=0;j<sk && j<10;++j)
                pf("%s\n",inp[res[j]].str);
        }
        DEL(head);
    }
    return 0;
}

/*
2
ab 10
ac 20
1
f

*/