QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726526#2924. Lone Rookzeyu#WA 23ms13680kbC++236.4kb2024-11-09 02:08:492024-11-09 02:08:50

Judging History

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

  • [2024-11-09 02:08:50]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:13680kb
  • [2024-11-09 02:08:49]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pl pair<ll, ll>
#define pi pair<int, int>
#define minpq priority_queue<ll, vector<ll>, greater<ll>>
using namespace std;

#if 1
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '['; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "]";}
void _print() {cerr << endl << flush;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "*["<<__LINE__<<"]\t"<< #x << " = "; _print(x)
#endif

const ll mod = 1e9 + 7;

template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll gcd(ll a, ll b) {if(b == 0){return a;} return gcd(b, a % b);}

const int maxn = 1000010;
int n, m;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
vector<int> graph[maxn];
vector<bool> vis(maxn);

int id(int r, int c){
	return r * m + c;
}

int p[maxn], sz[maxn];

int find(int x){
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}

void merge(int x, int y){
	int px = find(x);
	int py = find(y);
	p[px] = py;
	sz[py] += sz[px];
}

bool ingrid(int r, int c){
	return r >= 0 && r < n && c >= 0 && c < m;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i < maxn; i ++){
		p[i] = i; sz[i] = 1;
	}
	cin >> n >> m;
	vector<string> a(n);
	for (int i = 0; i < n; i ++) cin >> a[i];
	set<int> kid;
	int sid, eid;
	for (int i = 0; i < n; i ++){
		for (int j = 0; j < m; j ++){
			if (a[i][j] == 'K') kid.insert(id(i, j));
			if (a[i][j] == 'R') sid = id(i, j);
			if (a[i][j] == 'T') eid = id(i, j);
		}
	}
	for (int z : kid){
		for (int j = 0; j < 8; j ++){
			int nr = z / m + dx[j];
			int nc = z % m + dy[j];
			if (ingrid(nr, nc) && kid.find(id(nr, nc)) != kid.end()){
				if (find(z) != find(id(nr, nc))) merge(z, id(nr, nc));
			}
		}
	}
	vector<int> removed;
	for (int z : kid){
		if (sz[find(z)] == 1){
			removed.push_back(z);
			int r = z / m, c = z % m;
			a[r][c] = '.';
		}
	}
	// for (int i = 0; i < n; i ++){
	// 	for (int j = 0; j < m; j ++) cout << a[i][j];
	// 	cout << '\n';
	// }
	for (int i = 0; i < n; i ++){
		for (int j = 0; j < m; j ++){
			if (a[i][j] == 'K'){
				for (int k = 0; k < 8; k ++){
					int ni = i + dx[k];
					int nj = j + dy[k];
					if (ingrid(ni, nj) && a[ni][nj] != 'K'){
						a[ni][nj] = 'D';
					}
				}
			}
		}
	}
	// for (int i = 0; i < n; i ++){
	// 	for (int j = 0; j < m; j ++) cout << a[i][j];
	// 	cout << '\n';
	// }
	for (int i = 0; i < n; i ++){
		int s = 0, e = 0;
		while(s < m && e < m){
			while(s < m && (a[i][s] == 'D' || a[i][s] == 'K')) s ++;
			e = s + 1;
			bool good = true;
			while(e < m && (a[i][e] == 'D' || a[i][e] == 'K')){
				if (a[i][e] == 'K'){
					good = false;
					break;
				}
				e ++;
			}
			if (s < m && e < m && good){
				graph[id(i, s)].push_back(id(i, e));
				graph[id(i, e)].push_back(id(i, s));
			}
			s = e;
		}
	}
	for (int j = 0; j < m; j ++){
		int s = 0, e = 0;
		while(s < n && e < n){
			while(s < n && (a[s][j] == 'K' || a[s][j] == 'D')) s ++;
			e = s + 1;
			bool good = true;
			while(e < n && (a[e][j] == 'D' || a[e][j] == 'K')){
				if (a[e][j] == 'K'){
					good = false;
					break;
				}
				e ++;
			}
			if (s < n && e < n && good){
				graph[id(s, j)].push_back(id(e, j));
				graph[id(e, j)].push_back(id(s, j));
			}
			s = e;
		}
	}
	queue<int> que;
	que.push(sid);
	vis[sid] = true;
	while(! que.empty()){
		int q = que.front(); que.pop();
		for (int to : graph[q]){
			if (! vis[to]){
				que.push(to);
				vis[to] = true;
			}
		}
	}
	//cout << (vis[eid] ? "yes" : "no");
	for (int _ = 0; _ < 20; _ ++){
		for (int z : removed){
			if (vis[z]) continue;
			int r = z / m, c = z % m;
			a[r][c] = 'K';
		}
		vis.assign(maxn, false);
		for (int i = 0; i < maxn; i ++) graph[i].clear();
		for (int i = 0; i < n; i ++){
			for (int j = 0; j < m; j ++){
				if (a[i][j] == 'K'){
					for (int k = 0; k < 8; k ++){
						int ni = i + dx[k];
						int nj = j + dy[k];
						if (ingrid(ni, nj) && a[ni][nj] != 'K'){
							a[ni][nj] = 'D';
						}
					}
				}
			}
		}
		// for (int i = 0; i < n; i ++){
		// 	for (int j = 0; j < m; j ++) cout << a[i][j];
		// 	cout << '\n';
		// }
		for (int i = 0; i < n; i ++){
			int s = 0, e = 0;
			while(s < m && e < m){
				while(s < m && (a[i][s] == 'D' || a[i][s] == 'K')) s ++;
				e = s + 1;
				bool good = true;
				while(e < m && (a[i][e] == 'D' || a[i][e] == 'K')){
					if (a[i][e] == 'K'){
						good = false;
						break;
					}
					e ++;
				}
				if (s < m && e < m && good){
					graph[id(i, s)].push_back(id(i, e));
					graph[id(i, e)].push_back(id(i, s));
				}
				s = e;
			}
		}
		for (int j = 0; j < m; j ++){
			int s = 0, e = 0;
			while(s < n && e < n){
				while(s < n && (a[s][j] == 'K' || a[s][j] == 'D')) s ++;
				e = s + 1;
				bool good = true;
				while(e < n && (a[e][j] == 'D' || a[e][j] == 'K')){
					if (a[e][j] == 'K'){
						good = false;
						break;
					}
					e ++;
				}
				if (s < n && e < n && good){
					graph[id(s, j)].push_back(id(e, j));
					graph[id(e, j)].push_back(id(s, j));
				}
				s = e;
			}
		}
		que = queue<int>();
		que.push(sid);
		vis[sid] = true;
		while(! que.empty()){
			int q = que.front(); que.pop();
			for (int to : graph[q]){
				if (! vis[to]){
					que.push(to);
					vis[to] = true;
				}
			}
		}
	}
	cout << (vis[eid] ? "yes" : "no");
}
/*
4 3
.T.
.KK
.KK
RKK
*/

詳細信息

Test #1:

score: 100
Accepted
time: 18ms
memory: 12292kb

input:

2 2
KR
TK

output:

yes

result:

ok single line: 'yes'

Test #2:

score: 0
Accepted
time: 19ms
memory: 13536kb

input:

2 3
R.K
KKT

output:

yes

result:

ok single line: 'yes'

Test #3:

score: 0
Accepted
time: 19ms
memory: 11676kb

input:

5 3
KKT
.K.
K..
...
KKR

output:

yes

result:

ok single line: 'yes'

Test #4:

score: 0
Accepted
time: 23ms
memory: 12440kb

input:

2 4
R.KK
KK.T

output:

no

result:

ok single line: 'no'

Test #5:

score: -100
Wrong Answer
time: 19ms
memory: 13680kb

input:

2 5
RKKK.
...KT

output:

yes

result:

wrong answer 1st lines differ - expected: 'no', found: 'yes'