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

Re:谁能给我这道题的C++代码呢

Posted by CKboss at 2013-05-01 22:14:45 on Problem 1182
In Reply To:谁能给我这道题的C++代码呢 Posted by:1527352582 at 2012-07-05 17:16:16
>     本人用C++写了这道题目,但超时了所以想看看大家是怎么解决这个问题的。一来想知道大家的方法到底先进在哪里,而来也想知道大家是如何组织C++代码的。还有一个疑问就是这道题目给出样例我感觉有问题,错误的语句总数应当为2,那个1 5 5陈述句不应当判定为错误。
>      真心希望各位能够帮忙,QQ号码:1527352582,有愿意交流编程的请加我昵称:卡卡西
#include <cstdio>

using namespace std;

int p[50005];
int r[50005];
int N,D,K;

int found(int x)
{
    if(x==p[x])  return x;
    int t=p[x];
    p[x]=found(t);
    r[x]=(r[x]+r[t])%3;
    return p[x];
}

void Union(int a,int b,int d)
{
    int ra=found(a);
    int rb=found(b);

    p[ra]=rb;
    r[ra]=(r[b]-r[a]+3+d)%3;
}

int main()
{
    scanf("%d%d",&N,&K);
    int sum=0;
    for(int i=0;i<=N;i++)
    {
        p[i]=i;
        r[i]=0;
    }
    while(K--)
    {
        int a,b;
        scanf("%d%d%d",&D,&a,&b);
        if(a>N||b>N||(D==2&&a==b)) sum++;
        else
        {
            int ra=found(a);
            int rb=found(b);
            if(ra==rb)
            {
                 if((r[a]-r[b]+3)%3!=D-1)
                    sum++;
            }
            else
                Union(a,b,D-1);
        }

    }

    printf("%d\n",sum);

    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