本地AC提交WA(在别的评测站上过了luogu却wa了emm)

P3355 骑士共存问题

米斯兰达 @ 2018-12-20 18:37:43

蒟蒻求助qwq(T了8个,wa了两个,已经写成线性了为什么还是T了啊····)

#include<bits/stdc++.h> 
using namespace std; 
const int maxn=160000+5,jia[8]={-2,-2,-1,-1,1,1,2,2},jia1[8]={-1,1,-2,2,-2,2,-1,1}; 
bool Map[202][202],mark[maxn];
int Link[maxn],Next[maxn],cnt,End[maxn],Last[maxn];
queue<int> q; 
bool Find(int x) 
{ 
    for (int i=Last[x];i;i=Next[i]) 
    { 
        int j=End[i]; 
        if (!mark[j]) 
        { 
            mark[j]=true; 
            if (Link[j]==0||Find(Link[j])) 
            { 
                Link[j]=x; 
                return true; 
            } 
        } 
    } 
} 
void jian(int a,int b) 
{ 
    cnt++; 
    End[cnt]=b; 
    Next[cnt]=Last[a]; 
    Last[a]=cnt; 
} 
int main() 
{ 
//freopen("ceshi.in","r",stdin);
    int n,m; 
    scanf("%d%d",&n,&m); 
    for (int i=1;i<=m;i++) 
    {int a,b;scanf("%d%d",&a,&b);Map[a][b]=true;} 
    for (int i=1;i<=n;i++) 
        for (int j=1;j<=n;j++) 
        if (!Map[i][j]&&(i+j)%2==0) 
        {  
            q.push(((i-1)*n+j-1)/2+1);
            //这里就是标点啦,看不懂可以忽略掉emm
            for (int k=0;k<=7;k++) 
            { 
                int x=i+jia[k]; 
                int y=j+jia1[k]; 
                if (Map[x][y]||x>n||x<1||y>n||y<1) 
                continue; 
                jian(((i-1)*n+j-1)/2+1,((x-1)*n+y-1)/2+1); 
            }
        }
    int tot=0; 
    while (q.size()) 
    { 
        memset(mark,0,sizeof(mark)); 
        if (Find(q.front())) tot++;
        q.pop(); 
    } 
    printf("%d",n*n-m-tot); 
}

by RiverFun @ 2018-12-20 18:57:04

@米斯兰达 把mark数组开小一些


by 米斯兰达 @ 2018-12-20 19:07:49

@Steve_braveman mark开大开小不影响吧


by RiverFun @ 2018-12-20 19:23:37

@米斯兰达 memset很费时间的


by 米斯兰达 @ 2018-12-25 18:29:35

@Steve_braveman 谢谢大佬,但还是t了qwq,同时又wa了一个点,是代码不够优秀吗


by tuliwei @ 2019-01-31 09:37:44

数组开小了。


by tuliwei @ 2019-01-31 09:38:13

这题可能有720000条边


|