oj.uz

Submission #503533

# Submission time Handle Problem Language Result Execution time Memory
503533 2022-01-08T10:17:01 Z brayden04 Trampoline (info1cup20_trampoline) C++14
23 / 100
 1810 ms 20280 KB 
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

int R, C, N = 0;

bool trampolines[4005][4005];
bool visited[4005][4005];

int xStart = 0;
int yStart = 0;
int xEnd = 0;
int yEnd = 0;

bool dfs(int x, int y){
  if (visited[x][y] == true) return false;
  if (x > R || x < 1 || y > C || y < 1) return false;
  visited[x][y] = true;

  if (x == xEnd && y == yEnd){
    return true;
  }

  if (trampolines[x][y] == false){
    if (visited[x][y + 1] == false){
      dfs(x, y+1);
    }
  }
  else{
    if (visited[x + 1][y] == false){
      dfs(x + 1, y);
    }
    if (visited[x][y + 1] == false){
      dfs(x, y+1);
    }
  }
  return visited[xEnd][yEnd];
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  memset(trampolines, false, sizeof(trampolines[0][0])*2500*2500);
  cin >> R >> C >> N;

  for (int i = 0; i < N; i++){
    int temp1 = 0;
    int temp2 = 0;
    cin >> temp1 >> temp2;
    trampolines[temp1][temp2] = true;
  }

  int T = 0;
  cin >> T;

  for (int i = 0; i < T; i++){
    memset(visited, false, sizeof(visited[0][0])*2500*2500);

    cin >> xStart >> yStart >> xEnd >> yEnd;

    bool test = dfs(xStart, yStart);

    if (test){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 12552 KB 200 token(s): yes count is 21, no count is 179
2 Correct 66 ms 12552 KB 200 token(s): yes count is 70, no count is 130
3 Correct 46 ms 12540 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1810 ms 20280 KB expected NO, found YES [16th token]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 12876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 12856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 12876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -