Submission #1062200

#TimeUsernameProblemLanguageResultExecution timeMemory
1062200beaconmcToy (CEOI24_toy)C++14
35 / 100
42 ms13488 KiB
#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 (rowdist(i[0], i[1], node[0]) < k) continue; 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: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]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...