511 - Do You Know the Way to San Jose? - Do nothing AC

The forum to report every bug you find or tell us what you'd like to find in UVa OJ

Moderator: Board moderators

shtorm941
New poster
Posts: 7
Joined: Sat Mar 10, 2012 5:46 pm

Re: 200 - Rare Order(WA on Java)

Post by shtorm941 »

brianfry713 wrote:Print a newline at the end.
YES!!! thank you very much!!!

rambo1980
New poster
Posts: 15
Joined: Sun Mar 18, 2012 2:45 pm

Re: 200 - Rare Order(WA on Java)

Post by rambo1980 »

Anyone help me please, why am i getting WA for this problem? It gives me right answers for all testcases i found on the board.

Code: Select all

#include<iostream>
#include<stack>
#include<cstdio>
#include<cstring>

using namespace std;

struct index
{
    char str[25];
}str[200000];

struct adjacency
{
    char child[50],ancestor,children;
}list[150];

bool visited[150];
char order[150];
stack<int>s;

void build_seq(int size);
void process(char *a,char *b);
bool relation_present(char a,char b);
void create_index(int &total);

int main()
{
    int i,size;
    for(i='A';i<='Z';i++)
        visited[i]=list[i].ancestor=list[i].children=0;
    for(size=0;;size++)
    {
        scanf("%s",str[size].str);
        if(!strcmp(str[size].str,"#"))
        {
            build_seq(size);
            break;
        }
    }
    return 0;
}

void build_seq(int size)
{
    int i,total=0;
    for(i=1;i<size;i++)
        process(str[i-1].str,str[i].str);
    create_index(total);
    for(i=0;i<total;i++)
        putchar(order[i]);
    puts("");
}

void process(char *a,char *b)
{
    char *p,*q;
    for(p=a,q=b;*p&&*q;p++,q++)
    {
        if(*p!=*q)
        {
            if(!relation_present(*p,*q))
            {
                list[*p].child[list[*p].children++]=*q;
                list[*q].ancestor++;
				return;
            }
        }
    }
}

bool relation_present(char a,char b)
{
    int i;
    for(i=0;i<list[a].children;i++)
        if(list[a].child[i]==b)
            return 1;
    return 0;
}

void create_index(int &total)
{
    int i,temp,temp2;
    for(i='Z';i>='A';i--)
        if(list[i].children&&!list[i].ancestor)
        {
            visited[i]=true;
            s.push(i);
        }
    while(!s.empty())
    {
        temp=s.top();
        s.pop();
        order[total++]=temp;
        for(i=0;i<list[temp].children;i++)
        {
            temp2=list[temp].child[i];
            list[temp2].ancestor--;
            if(visited[temp2]==false&&!list[temp2].ancestor)
            {
                visited[temp2]=true;
                s.push(temp2);
            }
        }
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 200 - Rare Order(WA on Java)

Post by brianfry713 »

You don't need to post this in two threads.
Check input and AC output for thousands of problems on uDebug!

Locked

Return to “Bugs and suggestions”