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

遗留了若干月的问题……

Posted by 5D6D at 2012-09-25 17:41:06 on Problem 2513
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
const int NMax=500000;
struct trie
{
    int key;
    trie *c[26];
}*Root,pool[5000000];
int nn,L,father[NMax],G[NMax];
int Find(char a[])
{
    //int len=strlen(a);
    trie *p=Root;
    for(int i=0;a[i]!=0;i++)
    {
        if(!p) {return -1;}
        p=p->c[a[i]-'a'];
    }
    if(!p) {return -1;}
    return p->key;
}
int Insert(char a[])
{
    //int len=strlen(a);
    if(!Root)
    {
        trie *q=&pool[L++];
        q->key=-1;
        Root=q;
    }
    trie *p=Root;
    for(int i=0;a[i]!=0;i++)
    {
        if(p->c[a[i]-'a']==NULL)
        {
            trie *q=&pool[L++];
            q->key=-1;
            p->c[a[i]-'a']=q;
        }
        p=p->c[a[i]-'a'];
    }
    return (p->key=nn++);
}
int Find(int a)
{
    int R,s=a,tmp;
    for(R=a;father[R]>=0;R=father[R]);
    while(father[s]>=0)
    {
        tmp=father[s];
        father[s]=R;
        s=tmp;
    }
    return R;
}
void Union(int a,int b)
{
    int fa=Find(a),fb=Find(b);
    if(fa==fb) return ;
    father[fa]=fb;
}
int main()
{
    nn=0; L=0;
    memset(father,-1,sizeof(father));
    int tmp,tmp2;
    char buf1[15],buf2[15];
    bool has=0;
    Root=&pool[L++];
    while(scanf("%s%s",buf1,buf2)!=EOF)
    {
        //if(buf1[0]=='#' && buf2[0]=='#') break;
        has=1;
        //int la=strlen(buf1),lb=strlen(buf2);
        tmp=Find(buf1);
        if(tmp==-1)
            tmp=Insert(buf1);
        tmp2=Find(buf2);
        if(tmp2==-1)
            tmp2=Insert(buf2);
        G[tmp]++;
        G[tmp2]++;
        Union(tmp,tmp2);
    }
    bool flag=1;
    int tot=0;
    for(int i=0;i<nn;i++)
    {
        if(father[i]<0)
        {
            tot++;
            if(tot>1) 
            {
                flag=0;
                break;
            }
        }
    }
    if(flag)
    {
        tot=0;
        for(int i=0;i<nn;i++)
        {
            tmp=G[i];
            if(tmp%2!=0)
                tot++;
        }   
        if(tot!=2&&tot!=0) flag=0;
    }
    if(flag || !has) puts("Possible");
    else puts("Impossible");
    getchar(); getchar();
    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