oj.uz

Submission #1062198

# Submission time Handle Problem Language Result Execution time Memory
1062198 2024-08-16T21:20:45 Z beaconmc Toy (CEOI24_toy) C++14
0 / 100
 9 ms 12308 KB 
#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 sus[100000];

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();


	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);
	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]]){
				visited[i[0]][i[1]] = 1;
				if (coldist(i[0], i[1], node[1]) < l) continue;
				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]]){
				visited[i[0]][i[1]] = 1;
				if (coldist(i[0], i[1], node[0]) < k) continue;
				stack.push_back({i[0], i[1]});

			}
		}

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




}

Compilation message

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 7 ms 12308 KB Output is correct
5 Correct 9 ms 12184 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Incorrect 8 ms 11672 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 0 ms 2392 KB Output isn't correct
4 Halted 0 ms 0 KB -