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

WA 可以看看

Posted by 211550 at 2014-08-05 20:30:35 on Problem 1182




#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include<queue>
using namespace std;
#define lson ((root<<1)+1)
#define rson ((root<<1)+2)
#define MID ((l+r)>>1)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=100004;
const int base=1000;
const int inf=999999;
int a[maxn*3],rank[maxn*3];
void build(int n)
{
    for(int i=0;i<n;i++)
    {
        a[i]=i;
        rank[i]=0;
    }
}
int find(int n)
{
    if(a[n]!=n)a[n]=find(a[n]);
    return a[n];
}
void add(int x,int y)
{
    x=find(x);
    y=find(y);
    if(y==x)return;
    if(rank[x]<rank[y])
        a[x]=y;
    else
    {
        a[y]=x;
        if(rank[x]==rank[y])
            rank[x]++;
    }
}
bool same(int x,int y)
{
    return find(x)==find(y);
}
int T[maxn],X[maxn],Y[maxn];
int main()
{
    int n,m,k,i,j,t;scanf("%d%d",&n,&k);//单组输入  否则会WA
    //while(~))
    //{
        for(i=0;i<k;i++)
        {
            scanf("%d%d%d",&T[i],&X[i],&Y[i]);
        }
        build(n*3);
        int ans=0;
        for(i=0;i<k;i++)
        {
            t=T[i];
            int x=X[i]-1,y=Y[i]-1;
            if(x<0||x>=n||y<0||y>=n)
            {
                ans++;
                continue;
            }
            if(t==1)
            {
                if(same(x,y+n)||same(x,y+2*n))
                {
                    ans++;
                }
                else
                {
                    add(x,y);
                    add(x+n,y+n);
                    add(x+2*n,y+2*n);
                }
            }
            else
            {
                if(same(x,y)||same(x,y+2*n))
                    ans++;
                else
                {
                    add(x,y+n);
                    add(x+n,y+2*n);
                    add(x+2*n,y);
                }
            }
        }
        printf("%d\n",ans);
   // }
    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