Submission #1131250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131250		jpfr12	Trampoline (info1cup20_trampoline)	C++20	23 / 100	2094 ms	122852 KiB

trampoline

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long int ull;
using namespace std;
const ll MOD = (ll)1e9+7;
int MAXN = 1e6;

//classes


//global
int ROW, COL, N;
vector<vector<bool>> Green;
vector<vector<bool>> vis;

bool bfs(int Rs, int Cs, int Re, int Ce){
  vis[Rs][Cs] = true;
  queue<pair<int,int>> Q;
  Q.emplace(Rs, Cs);
  while(!Q.empty()){
    pair<int,int> p = Q.front();
    Q.pop();
    int x = p.first;
    int y = p.second;
    if(x == Re && y == Ce) return true;
    if(Green[x][y]){
      if(x+1 < ROW && !vis[x+1][y]){
        vis[x+1][y] = true;
        Q.emplace(x+1, y);
      }
      if(y+1 < COL && !vis[x][y+1]){
        vis[x][y+1] = true;
        Q.emplace(x, y+1);
      }
    }
    else{
      if(y+1 < COL && !vis[x][y+1]){
        vis[x][y+1] = true;
        Q.emplace(x, y+1);
      }
    }
  }
  return false;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  //ifstream fin("hps.in");
  //ofstream fout("hps.out");
  //stop
  cin >> ROW >> COL >> N;
  Green.resize(ROW, vector<bool>(COL, false));
  vis.resize(ROW, vector<bool>(COL, false));
  for(int i = 0; i < N; i++){
    int a, b;
    cin >> a >> b;
    Green[a-1][b-1] = true;
  }
  int T;
  cin >> T;
  while(T--){
    int Rstart, Cstart, Rend, Cend;
    cin >> Rstart >> Cstart >> Rend >> Cend;
    if(bfs(Rstart-1, Cstart-1, Rend-1, Cend-1)) cout << "Yes\n";
    else cout << "No\n";
    vis.assign(ROW, vector<bool>(COL, false));
  }
  return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 27