Submission #50072514

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
int read(){int r;scanf("%d",&r);return r;}
const int N=1010,M=1000010;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
int h,w;
int dfn[N][N],low[N][N];
int f[N][N]; // 相连的 点-双连通分量 数量 -1
int cnt[M]; // 单连通块[b]大小
int bl[N][N]; // bl[x][y] = 单连通块id
char s[N][N];
void tarjan(int x,int y,int fx,int fy,int b,int dep=1){
  low[x][y]=dfn[x][y]=dep; // 有向图 ++tick;, 无向图可以直接dep
  cnt[bl[x][y]=b]++;
  rep(i,0,4) {
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(nx<1||nx>h||ny<1||ny>w||s[nx][ny]=='.') continue;
    if(!dfn[nx][ny]){
      tarjan(nx,ny,x,y,b,dep+1);
      low[x][y]=min(low[x][y],low[nx][ny]);
      if(low[nx][ny]>=dfn[x][y]) f[x][y]++;
    }else if(nx != fx or ny != fy){ // 非回边
      low[x][y]=min(low[x][y],dfn[nx][ny]); // 这里不是low 是dfn, 同样是8字形的问题
    }
  }
  if(x==fx and y==fy) f[x][y]--; // root
}
int main(){
  h=read();
  w=read();
  rep(i,1,h+1) scanf("%s",s[i]+1);
  int t=0;
  rep(i,1,h+1) rep(j,1,w+1) if(s[i][j]=='#' && !dfn[i][j]) tarjan(i,j,i,j,++t);
  mint a1=0;
  mint a2=0;
  rep(i,1,h+1) rep(j,1,w+1) if(s[i][j]=='#'){
    a1 ++;
    a2 += (cnt[bl[i][j]]==1)?-1:f[i][j];
  }
  printf("%d\n",(a2*a1.pow(MOD-2)+t).val()); // a1可能为0 不要inv()
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int read()’:
Main.cpp:7:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    7 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:37:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |   rep(i,1,h+1) scanf("%s",s[i]+1);
      |                ~~~~~^~~~~~~~~~~~~

Judge Result