QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#270976#2924. Lone RookPetroTarnavskyi#AC ✓351ms83424kbC++203.8kb2023-12-01 19:11:062023-12-01 19:11:07

Judging History

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

  • [2023-12-01 19:11:07]
  • 评测
  • 测评结果:AC
  • 用时:351ms
  • 内存:83424kb
  • [2023-12-01 19:11:06]
  • 提交

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'