QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#270976 | #2924. Lone Rook | PetroTarnavskyi# | AC ✓ | 351ms | 83424kb | C++20 | 3.8kb | 2023-12-01 19:11:06 | 2023-12-01 19:11:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 777;
string grid[N];
int cnt[N][N];
set<int> horsesRow[N], horsesCol[N];
set<int> freeRow[N], freeCol[N];
int n, m;
struct DSU
{
VI p, sz;
vector<VI> horses;
void init()
{
p.resize(n * m);
iota(ALL(p), 0);
sz.assign(n * m, 1);
horses.resize(n * m);
FOR(i, 0, n)
FOR(j, 0, m)
if(grid[i][j] == 'K')
horses[i * m + j].PB(i * m + j);
}
int par(int v)
{
if(p[v] == v)
return v;
return p[v] = par(p[v]);
}
bool merge(int u, int v)
{
u = par(u);
v = par(v);
if(u == v)
return false;
if(sz[u] > sz[v])
swap(u, v);
p[u] = v;
sz[v] += sz[u];
if(SZ(horses[v]) < SZ(horses[u]))
swap(horses[v], horses[u]);
horses[v].insert(horses[v].end(), ALL(horses[u]));
return true;
}
}dsu;
int dx[8] = {-1, -1, 1, 1, -2, -2, 2, 2};
int dy[8] = {-2, 2, -2, 2, -1, 1, -1, 1};
bool ok(int i, int j)
{
return 0 <= i && i < n && 0 <= j && j < m;
}
void add(int i, int j)
{
freeRow[i].insert(j);
freeCol[j].insert(i);
auto freeIt = freeRow[i].upper_bound(j);
auto horseIt = horsesRow[i].upper_bound(j);
if(freeIt != freeRow[i].end() && (horseIt == horsesRow[i].end() || *freeIt < *horseIt))
dsu.merge(i * m + j, i * m + (*freeIt));
freeIt = freeRow[i].lower_bound(j);
horseIt = horsesRow[i].lower_bound(j);
if(freeIt != freeRow[i].begin() && (horseIt == horsesRow[i].begin() || *prev(freeIt) > *prev(horseIt)))
dsu.merge(i * m + j, i * m + (*prev(freeIt)));
freeIt = freeCol[j].upper_bound(i);
horseIt = horsesCol[j].upper_bound(i);
if(freeIt != freeCol[j].end() && (horseIt == horsesCol[j].end() || *freeIt < *horseIt))
dsu.merge(i * m + j, (*freeIt) * m + j);
freeIt = freeCol[j].lower_bound(i);
horseIt = horsesCol[j].lower_bound(i);
if(freeIt != freeCol[j].begin() && (horseIt == horsesCol[j].begin() || *prev(freeIt) > *prev(horseIt)))
dsu.merge(i * m + j, (*prev(freeIt)) * m + j);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
cin >> n >> m;
FOR(i, 0, n)
cin >> grid[i];
dsu.init();
FOR(i, 0, n)
{
FOR(j, 0, m)
{
if(grid[i][j] != 'K')
continue;
FOR(it, 0, 8)
{
int ni = i + dx[it], nj = j + dy[it];
if(ok(ni, nj))
cnt[ni][nj]++;
}
}
}
int start = -1, target = -1;
FOR(i, 0, n)
{
FOR(j, 0, m)
{
if(cnt[i][j] == 0)
{
freeRow[i].insert(j);
freeCol[j].insert(i);
}
else
{
if(grid[i][j] == 'K')
{
horsesRow[i].insert(j);
horsesCol[j].insert(i);
}
}
}
}
FOR(i, 0, n)
{
FOR(j, 0, m)
{
if(cnt[i][j] == 0)
add(i, j);
if(grid[i][j] == 'R')
start = i * m + j;
if(grid[i][j] == 'T')
target = i * m + j;
}
}
while(true)
{
if(dsu.par(start) == dsu.par(target))
break;
int v = dsu.par(start);
if(SZ(dsu.horses[v]) == 0)
break;
VI horses = dsu.horses[v];
dsu.horses[v].clear();
for(int horse : horses)
{
int i = horse / m;
int j = horse % m;
FOR(it, 0, 8)
{
int ni = i + dx[it], nj = j + dy[it];
if(!ok(ni, nj))
continue;
cnt[ni][nj]--;
if(cnt[ni][nj] == 0)
{
add(ni, nj);
}
}
}
}
if(dsu.par(start) == dsu.par(target))
cout << "yes\n";
else
cout << "no\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3616kb
input:
2 2 KR TK
output:
yes
result:
ok single line: 'yes'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
2 3 R.K KKT
output:
yes
result:
ok single line: 'yes'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
5 3 KKT .K. K.. ... KKR
output:
yes
result:
ok single line: 'yes'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
2 4 R.KK KK.T
output:
no
result:
ok single line: 'no'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
2 5 RKKK. ...KT
output:
no
result:
ok single line: 'no'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
5 6 .....T ..K... ..KK.. ...K.. R.....
output:
no
result:
ok single line: 'no'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
3 4 ...K T.KR ..K.
output:
no
result:
ok single line: 'no'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
6 3 .R. ... ... KKK .K. .T.
output:
yes
result:
ok single line: 'yes'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
6 6 ..K..T ..K... ...... ..KK.K ...K.. R.....
output:
no
result:
ok single line: 'no'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
6 6 ..K... ..KTK. ...... ..KK.. ...K.. R.....
output:
yes
result:
ok single line: 'yes'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
14 6 T.K..K ...... K....K KKK.KK KKK.KK ...... ...... ..K.KK .K...K ...... ..KK.K ...K.. ...... R.K.K.
output:
yes
result:
ok single line: 'yes'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
9 12 R...K.....KK ...KKK.T..KK ...K......KK ...K......KK .....K....KK ..........KK KK.......KKK .KK...K..KKK ..K......KKK
output:
yes
result:
ok single line: 'yes'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
17 14 ......KK...... ......KK...... RKK...KK...... K.....KKKK...K ......KKKK..KK ......KKKK..KK ...KKKKK.....K ..K.KKKKK..... ............K. ............K. ....K......... ...........KK. KKKKKKKKKK.KK. KK..KKKKK..... T............. ...K.......K.. .........KKKKK
output:
yes
result:
ok single line: 'yes'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
10 10 .K.K.K.K.T K.K.K.K.K. .K.K.K.K.K K.K.K.K.K. .K.K.K.K.K K.K.K.K.K. .K.K.K.K.K K.K.K.K.K. .K.K.K.K.K R.K.K.K.K.
output:
no
result:
ok single line: 'no'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
4 3 K.T ... .K. R..
output:
no
result:
ok single line: 'no'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
4 3 ..T ... .K. R..
output:
yes
result:
ok single line: 'yes'
Test #17:
score: 0
Accepted
time: 38ms
memory: 25400kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #18:
score: 0
Accepted
time: 35ms
memory: 27016kb
input:
500 500 R..KK..................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #19:
score: 0
Accepted
time: 104ms
memory: 51808kb
input:
742 741 KKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KK...
output:
no
result:
ok single line: 'no'
Test #20:
score: 0
Accepted
time: 128ms
memory: 51800kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
no
result:
ok single line: 'no'
Test #21:
score: 0
Accepted
time: 106ms
memory: 51916kb
input:
742 741 KKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KKKKKKKKKKKKKKKKKK.KKKKKK.KK...
output:
yes
result:
ok single line: 'yes'
Test #22:
score: 0
Accepted
time: 109ms
memory: 51908kb
input:
741 742 K..KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #23:
score: 0
Accepted
time: 265ms
memory: 61980kb
input:
750 750 R.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.KKK.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K....
output:
yes
result:
ok single line: 'yes'
Test #24:
score: 0
Accepted
time: 291ms
memory: 61896kb
input:
750 750 R.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.KKK.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.KKK.K.KKK.K.K.K.K.K.KKK.K.K.K.K....
output:
yes
result:
ok single line: 'yes'
Test #25:
score: 0
Accepted
time: 282ms
memory: 60940kb
input:
750 750 R.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K....
output:
no
result:
ok single line: 'no'
Test #26:
score: 0
Accepted
time: 277ms
memory: 61196kb
input:
750 750 R.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.KKK.K.K.K.KKK.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K.K....
output:
no
result:
ok single line: 'no'
Test #27:
score: 0
Accepted
time: 97ms
memory: 53612kb
input:
744 750 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #28:
score: 0
Accepted
time: 101ms
memory: 54368kb
input:
747 747 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #29:
score: 0
Accepted
time: 141ms
memory: 56940kb
input:
748 748 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK...
output:
yes
result:
ok single line: 'yes'
Test #30:
score: 0
Accepted
time: 58ms
memory: 37944kb
input:
750 750 .......................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #31:
score: 0
Accepted
time: 351ms
memory: 73284kb
input:
750 750 .....................K........................................................................................................K................................................................................................................................................K.......................
output:
yes
result:
ok single line: 'yes'
Test #32:
score: 0
Accepted
time: 342ms
memory: 68812kb
input:
750 750 .....................K................................................................................K.......................K.K..............................................................................................................................................K.......................
output:
yes
result:
ok single line: 'yes'
Test #33:
score: 0
Accepted
time: 234ms
memory: 55552kb
input:
750 750 ..K........K..K......K.....................K.........................K.....................K..........K.......................K.K..............................................................................................................................................K.......................
output:
yes
result:
ok single line: 'yes'
Test #34:
score: 0
Accepted
time: 343ms
memory: 73272kb
input:
750 750 .....................K........................................................................................................K................................................................................................................................................K.......................
output:
no
result:
ok single line: 'no'
Test #35:
score: 0
Accepted
time: 343ms
memory: 68640kb
input:
750 750 .....................K................................................................................K.......................K.K..............................................................................................................................................K.......................
output:
no
result:
ok single line: 'no'
Test #36:
score: 0
Accepted
time: 255ms
memory: 57812kb
input:
750 750 ..K........K..K......K.....................K.........................K.....................K..........K.......................K.K..............................................................................................................................................K.......................
output:
no
result:
ok single line: 'no'
Test #37:
score: 0
Accepted
time: 47ms
memory: 38556kb
input:
750 750 .......................................................................................................................................................................................................................................................................................................
output:
yes
result:
ok single line: 'yes'
Test #38:
score: 0
Accepted
time: 96ms
memory: 41336kb
input:
750 750 K........K..................K.................................K...........KK..........................................K...........K.....K.......K.............................K.................................K.............................................K...............K........................
output:
yes
result:
ok single line: 'yes'
Test #39:
score: 0
Accepted
time: 331ms
memory: 73584kb
input:
750 750 ....................................................................................................................................................................................................................................................................................K..................
output:
yes
result:
ok single line: 'yes'
Test #40:
score: 0
Accepted
time: 101ms
memory: 41488kb
input:
750 750 ......K....K.................................K...........K.......K..............K.............................................K.................................................K...K.....................................KK............K....................................K...KK.K..................
output:
yes
result:
ok single line: 'yes'
Test #41:
score: 0
Accepted
time: 227ms
memory: 54396kb
input:
750 750 K........K..................K.................................K...........KK..........................................K...........K.....K.......K.............................K.................................K.............................................K...............K........................
output:
no
result:
ok single line: 'no'
Test #42:
score: 0
Accepted
time: 99ms
memory: 41272kb
input:
750 750 ......K.K..................K......K...K...............K..K............K.........K...............................................................K.....K...............K..K..................................K..K...K..........K....................K.........KKK............................K.K..K.....
output:
no
result:
ok single line: 'no'
Test #43:
score: 0
Accepted
time: 239ms
memory: 54904kb
input:
750 750 ......K....K.................................K...........K.......K..............K.............................................K.................................................K...K.....................................KK............K....................................K...KK.K..................
output:
no
result:
ok single line: 'no'
Test #44:
score: 0
Accepted
time: 245ms
memory: 83424kb
input:
750 750 R..KK..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K..K.....
output:
yes
result:
ok single line: 'yes'
Test #45:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
6 6 .....T ..K.K. K.K... ....K. R..K.. ....K.
output:
yes
result:
ok single line: 'yes'
Test #46:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
3 4 RK.. KK.. ...T
output:
yes
result:
ok single line: 'yes'
Test #47:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
4 4 .K.. KR.. K... .K.T
output:
no
result:
ok single line: 'no'