Submission #1062212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062212		beaconmc	Toy (CEOI24_toy)	C++14	100 / 100	483 ms	121904 KiB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;


ll grid[2000][2000];
vector<ll> rows[2000];
vector<ll> cols[2000];
bool visited[2000][2000];


ll rowdist(ll a, ll b, ll c){

	ll sus = upper_bound(rows[a].begin(), rows[a].end(), b) - rows[a].begin();

	ll sus2 = upper_bound(rows[c].begin(), rows[c].end(), b) - rows[c].begin();

	ll left = max(rows[a][sus-1], rows[c][sus2-1]);
	ll right = min(rows[a][sus], rows[c][sus2]);


	ll ans = 1;
	ans += right-b-1;
	ans += b-left-1;
	return ans;
}

ll coldist(ll a, ll b, ll c){
	ll sus = upper_bound(cols[b].begin(), cols[b].end(), a) - cols[b].begin();
	ll sus2 = upper_bound(cols[c].begin(), cols[c].end(), a) - cols[c].begin();
	// cout << sus << " " << sus2 << endl;
	// for (auto&i : cols[b]){
	// 	cout << i << " ";
	// }
	// cout << endl;


	ll left = max(cols[b][sus-1], cols[c][sus2-1]);
	ll right = min(cols[b][sus], cols[c][sus2]);

	ll ans = 1;
	ans += right-a-1;
	ans += a-left-1;
	return ans;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	FOR(i,0,2000) rows[i].clear(), cols[i].clear();
	FOR(i,0,2000) FOR(j,0,2000) grid[i][j] = 0, visited[i][j] = 0;
	ll w,h,k,l;
	cin >> w >> h >> k >> l;

	ll a,b,c,d;
	cin >> a >> b >> c >> d;
	a = b; b = c;
	ll x,y;

	FOR(i,0,h){
		string temp;
		cin >> temp;
		FOR(j,0,w){
			visited[i][j] = 0;
			grid[i][j] = temp[j];

			if (grid[i][j] == 'X'){
				rows[i].push_back(j);
				cols[j].push_back(i);
			}
			if (grid[i][j] == '*'){
				x=i;
				y=j;
			}
		}
	}


	FOR(i,0,h) rows[i].push_back(-1), rows[i].push_back(w), sort(rows[i].begin(), rows[i].end());
	FOR(i,0,w) cols[i].push_back(-1), cols[i].push_back(h), sort(cols[i].begin(), cols[i].end());




	// FOR(i,0,h){
	// 	FOR(j,0,w){
	// 		cout << (char) grid[i][j];
	// 	}
	// 	cout << endl;
	// }








	bool flag = false;

	vector<vector<ll>> stack;

	stack.push_back({a,b});
	visited[a][b] = true;
	while (stack.size()){


		vector<ll> node = stack[stack.size()-1];



		if (node[0] == x && node[1] == y){
			flag = true;
			break;
		}
		stack.pop_back();

		vector<vector<ll>> nxt = {{node[0], node[1]+1},{node[0], node[1]-1}};
		vector<vector<ll>> nxt2 = {{node[0]+1, node[1]},{node[0]-1, node[1]}};

		for (auto&i : nxt){
			if (0<=i[0] && i[0] < h && 0<=i[1] && i[1] < w && grid[i[0]][i[1]] != 'X' && !visited[i[0]][i[1]]){
				
				if (coldist(i[0], i[1], node[1]) < l) continue;
				visited[i[0]][i[1]] = 1;
				stack.push_back({i[0], i[1]});

			}
		}
		for (auto&i : nxt2){
			if (0<=i[0] && i[0] < h && 0<=i[1] && i[1] < w && grid[i[0]][i[1]] != 'X' && !visited[i[0]][i[1]]){
				
				if (rowdist(i[0], i[1], node[0]) < k) continue;
				visited[i[0]][i[1]] = 1;
				stack.push_back({i[0], i[1]});

			}
		}

	}
	if (flag) cout << "YES";
	else cout << "NO";




}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:119:20: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |   if (node[0] == x && node[1] == y){
Main.cpp:119:20: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27