QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#432758 | #8742. 黑白 | Physics212303 | AC ✓ | 65ms | 12356kb | C++17 | 1.4kb | 2024-06-07 16:43:13 | 2024-06-07 16:43:13 |
Judging History
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