2015年4月20日 星期一

2015/04/20 Codeforces 2A. Winner

/*
    閒閒來寫 Trie~~
    自然被別人輕鬆用 map屌打 xDDD
*/
// http://codeforces.com/problemset/problem/2/A
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct Node
{
    Node *ch[30]; int num, id;
    Node(){ fill(ch, ch+30, nullptr); num = id = 0; }
};

Node *root = new Node();
int clk = 0;

vector<int> v;
vector<Node*> ptr;

int goal;

void add(char *c, int x)
{
    Node *now = root;

    while(*c)
    {
        if( !now->ch[*c-'a'] )
        {
            now->ch[*c-'a'] = new Node();
            now->ch[*c-'a']->id = clk++;
            ptr.push_back(now->ch[*c-'a'] );
        }
        now = now->ch[*c-'a']; c++;
    }

    now->num += x;
    if( now->num > 0 ) v.push_back(now->id), v.push_back(now->num);

}

deque<int> deq;

void DFS(Node *O)
{
    if( O->id == goal )
    {
        for(int di = 0; di < deq.size(); di++)
            printf("%c", deq[di]+'a');
    }

    for(int i = 0; i < 30; i++)
    {
        if( O->ch[i] )
        {
            deq.push_back(i);
            DFS(O->ch[i] );
            deq.pop_back();
        }
    }
}

int N;
char s[40];

int main()
{
    scanf("%d", &N);

    for(int Ni = 0; Ni < N; Ni++)
    {
        int x;
        scanf("%s %d", s, &x);
        add(s, x);
    }

    int mx = 0;

    for(int pi = 0; pi < ptr.size(); pi++)
        mx = max(mx, ptr[pi]->num);

    for(int vi = 0; vi < v.size(); vi+=2)
        if( ptr[v[vi] ]->num == mx && v[vi+1] >= mx )
        {
            goal = ptr[v[vi] ]->id;
            break;
        }

    DFS(root); puts("");
}

沒有留言:

張貼留言