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

看,我的70l,就是速度有点慢

Posted by morenan at 2010-09-26 00:03:15 on Problem 1021
In Reply To:居然一次AC,分享下代码,仅供参考,140行C++,0ms Posted by:sbtdkj1017 at 2010-09-13 23:35:05
#include<iostream>
#include<stdio.h>
#include<map>
#define MAXN 110
#define MAXM 300010
#define MO 19931219
#define FOR(i,l,r) for (i=l;i<=r;i++)
#define COR(i,r,l) for (i=r;i>=l;i--)
#define M(a) memset(a,0,sizeof(a))
using namespace std;
map <unsigned int,int> Map;
int i,j,k,l,m,n,ca,tim,bet;
static int a[2][MAXN][MAXN],q[MAXN][MAXN],cx[MAXM],cy[MAXM];
const int wy[4]={0,-1,0,1},wx[4]={1,0,-1,0};
bool check(int x,int y) {
     return (x && x<=n && y && y<=m);}
unsigned int ram(int fri) {
         return bet=(bet*fri+234645)%MO;}
void flood(int x,int y,int g,int dx,int dy,int co) {
     int l1=0,l2=1,fin,nx,ny,i,j,k;
     cx[1]=x;cy[1]=y;q[x][y]=1;
     unsigned int hash=19931219;bet=hash;
     while (l1<l2) for (x=cx[++l1],y=cy[l1],k=0;k<=3;k++) {
           nx=x+wx[(k+g)%4]*dx;ny=y+wy[(k+g)%4]*dy;
           if (check(nx,ny) && a[co][nx][ny] && !q[nx][ny]) {
              q[nx][ny]=1;cx[++l2]=nx;cy[l2]=ny;
              hash=((hash+ram(l1))*k+ram(l2)*(k*k+12))*(k+hash+2345);
           }
     }
     if (co) Map[hash]++;
        else if (Map[hash]) {
             Map[hash]--;
             FOR(i,1,l2) a[0][cx[i]][cy[i]]=0;
        }
}
int main() {
    for (scanf("%d",&ca);ca;ca--,M(a)) {
        scanf("%d%d%d",&n,&m,&tim);
        FOR(i,1,tim) {
           scanf("%d%d",&j,&k);j++;k++;
           a[0][j][k]=1;}
        FOR(i,1,tim) {
           scanf("%d%d",&j,&k);j++;k++;
           a[1][j][k]=1;}
        M(q);FOR(i,1,n) FOR(j,1,m) if (a[1][i][j] && !q[i][j]) flood(i,j,0,1,1,1);
        M(q);FOR(i,1,n) FOR(j,1,m) if (a[0][i][j] && !q[i][j]) flood(i,j,0,1,1,0);
        M(q);COR(i,n,1) FOR(j,1,m) if (a[0][i][j] && !q[i][j]) flood(i,j,0,-1,1,0);
        
        M(q);FOR(j,1,m) COR(i,n,1) if (a[0][i][j] && !q[i][j]) flood(i,j,3,1,1,0);
        M(q);COR(j,m,1) COR(i,n,1) if (a[0][i][j] && !q[i][j]) flood(i,j,3,1,-1,0);
        
        M(q);COR(i,n,1) COR(j,m,1) if (a[0][i][j] && !q[i][j]) flood(i,j,2,1,1,0);
        M(q);FOR(i,1,n) COR(j,m,1) if (a[0][i][j] && !q[i][j]) flood(i,j,2,-1,1,0);
        
        M(q);COR(j,m,1) FOR(i,1,n) if (a[0][i][j] && !q[i][j]) flood(i,j,1,1,1,0);
        M(q);FOR(j,1,m) FOR(i,1,n) if (a[0][i][j] && !q[i][j]) flood(i,j,1,1,-1,0);
        FOR(i,1,n) {
           FOR(j,1,m) if (a[0][i][j]) break;
           if (j<=m) break;
        }
        if (i>n && j>m) printf("YES\n");
           else printf("NO\n");
        Map.clear();
    }
    return 1;
}

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