Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:测试数据

Posted by Karlvin at 2011-11-09 16:49:09 on Problem 1094
In Reply To:测试数据 Posted by:qlyzpqz at 2009-11-07 22:54:20
这里给的样例我都能通过为什么提交还是WA呢?
这是我的代码:
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<set>
using namespace std;
bool emerge[26];
int step[26];
struct vec
{
       int ins;
       int id;
       set<int> outs;
}graph[26];
void initial()
{
     memset(emerge,0,sizeof(emerge));
    
     for(int i=0;i<26;i++)
     {   graph[i].ins=0;
         graph[i].id=i;
         graph[i].outs.clear();
         step[i]=1;
         }
}
class mySort
{
      private:
              char letters[1000000];
              int chars;
              int relations;
              int SUM;
              int line;
              int state;
              string answer;
              int left;
              int right;
      public :
             int input();
             void compute();
             void print();
             int relationConfirmed();
             void checkOut(int entrance);
             int refreshStep(int entrance);
};
int mySort::input()
{
     cin>>chars>>relations;
     if(chars ==0 && relations==0)
              return 0;
     char c='<';     
     initial();
     SUM=0;
     state=2;
     answer.resize(chars);
     for(int i=0;i<relations;i++)
         cin>>letters[SUM++]>>c>>letters[SUM++];
}
void mySort::compute()
{
     for(line=0;line< SUM/2;line++)  
     {
          left= letters[line*2]-'A';
          right= letters[line*2+1]-'A';
          graph[right].ins=1;
          graph[left].outs.insert(right) ;
          emerge[left]=true;
          emerge[right]= true; 
          if(relationConfirmed())
                break;     
          if(state==0)
          {   int entrance=0;
              for(int i=25;i>=0;i--)
                if(emerge[i]==true && graph[i].ins==0)
                {     entrance=i;
                      break;
                      }
            checkOut(entrance);
            break;  }
          }
}
void mySort::print()
{
     switch(state)
     {    case 0:  cout<<"Sorted sequence determined after "<<line+1<<" relations: "<<answer<<'.'<<endl;
                   break;
          case 1:  cout<<"Inconsistency found after "<<line+1<<" relations."<<endl;
                   break;
          case 2: cout<<"Sorted sequence cannot be determined."<<endl;
          }
}

void mySort::checkOut(int entrance)
{
    answer[0]=char(entrance+'A');
    int array[27]={0};
    int i=0;
    for( i=25;i>=0;i--)
         array[step[i]-1]=i;
    for(i=1;i<chars;i++)
       answer[i]=char(array[i]+'A');
}

int mySort::relationConfirmed()
{    
    if(step[right]<=step[left])
            step[right]=step[left]+1;
    return refreshStep(right);
} 
int mySort::refreshStep(int entrance)
{
    int flag=0;
    if(step[entrance]==chars)
            state=0;
    else if(step[entrance] > chars)
    {    state= 1;
         return 1;  }
     set<int>::iterator ip,end=graph[entrance].outs.end();      
     for(ip=graph[entrance].outs.begin(); ip!=end; ip++)
     {      
            if(step[*ip]<=step[entrance])
            {   step[*ip]=step[entrance]+1;
                flag=refreshStep(*ip);    }
            if(flag==1)
                  break;
            }
     return flag;
}
int main()
{
    mySort test;
    while(test.input())
    {
           test.compute();
           test.print();
           }
    return 0;
}
            

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator