QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#432758#8742. 黑白Physics212303AC ✓65ms12356kbC++171.4kb2024-06-07 16:43:132024-06-07 16:43:13

Judging History

你现在查看的是最新测评结果

  • [2024-06-07 16:43:13]
  • 评测
  • 测评结果:AC
  • 用时:65ms
  • 内存:12356kb
  • [2024-06-07 16:43:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s;
    public:
      dsu(){
        a.resize(200000),s.resize(200000,1);
        iota(a.begin(),a.end(),0);
      }
      dsu(int n){
        a.resize(n),s.resize(n,1);
        iota(a.begin(),a.end(),0);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      inline int size(T x){
        return s[leader(x)];
      }
      inline void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      inline bool same(T x,T y){
        return leader(x)==leader(y);
      }
  };
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n,m,c=0; cin>>n>>m;
    vector<string> s(n);
    for(auto &i:s){
      cin>>i; for(char j:i)c+=j=='W';
    }
    auto f=[&](int x,int y){return x*m+y;};
    IAOI_lib::dsu<int> d(n*m);
    for(int i=1;i<n;i++)
      for(int j=0;j<m;j++)
        if(s[i-1][j]=='W'&&s[i][j]=='W')
          d.merge(f(i-1,j),f(i,j));
    for(int i=0;i<n;i++)
      for(int j=1;j<m;j++)
        if(s[i][j-1]=='W'&&s[i][j]=='W')
          d.merge(f(i,j-1),f(i,j));
    cout<<(d.same(f(0,0),f(n-1,m-1))&&!(c+n+m&1)?"I\n":"J\n");
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 65ms
memory: 12356kb

input:

100
2 6
WWBBWW
WWWWWB
3 8
WWWBBBBB
WWWBWWWB
BBWWWBWW
5 2
WB
BB
BB
BW
BB
6 4
WWBW
WBWB
WWWW
WWWB
BBWW
BWBW
2 3
WWW
WBW
124 125
BWWWWWWWWWWWWWWWWWWWWWWWWWWBWWWWBWWWWWWWWBWWWWWWWWWWWBBBBWWWWWWWWWWWWWWWWWBWWWWWWWWWBWWWWWWWWWWBWWWWWWWWBBWWWWWWWWWWWWWWWWWWB
WWWWWWWBWWBWWWWWWWWWWWBWWBWWBWWWWBWWWWWWWWWBWBWB...

output:

J
J
J
I
I
J
I
I
I
J
I
J
J
J
J
J
I
I
I
I
J
J
I
I
I
J
J
I
J
J
J
J
I
J
J
J
J
J
J
I
J
J
I
I
I
J
J
I
J
J
J
I
J
I
J
J
J
J
I
I
J
J
J
I
J
J
I
J
I
I
J
J
J
I
J
I
I
J
J
I
J
J
J
J
J
I
J
J
J
I
I
J
J
I
I
J
J
J
J
I

result:

ok 100 lines