| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:谁能给我这道题的C++代码呢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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator