oj.uz

Submission #475212

# Submission time Handle Problem Language Result Execution time Memory
475212 2021-09-21T13:23:49 Z bigo Trampoline (info1cup20_trampoline) C++14
23 / 100
 1362 ms 27464 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
#define pii pair<int, int>
vector<vector<int>>vec;
vector<bool>visit;
void dfs(int v) {
	visit[v] = true;
	for (auto u:vec[v]) {
		if (!visit[u])
			dfs(u);
	}
}
int main() {
	int r, c, n;
	cin >> r >> c >> n;
	if (r <= 200 and c <= 200) {
		set<pii>green;
		int a, b;
		for (int i = 0; i < n; i++) {
			cin >> a >> b;
			a--, b--;
			green.insert({ a,b });
		}
		vec.resize(r * c);
		visit.resize(r * c, false);
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (green.find({ i,j }) != green.end()) {
					if (j != c - 1)
						vec[i * c + j].push_back(i * c + j + 1);
					if (i != r - 1)
						vec[i * c + j].push_back((i + 1) * c + j);
				}
				else {
					if (j != c - 1)
						vec[i * c + j].push_back(i * c + j + 1);
				}
			}
		}
		int t;
		cin >> t;
		while (t--) {
			int y1, x1, y2, x2;
			cin >> y1 >> x1 >> y2 >> x2;
			y1--, x1--, y2--, x2--;
			dfs(y1 * c + x1);
			if (visit[y2 * c + x2])
				cout << "YES";
			else
				cout << "NO";
			cout << endl;
			visit.resize(0);
			visit.resize(r * c, false);
		}
	}
	else {
		set<pii>green;
		set<int>green1;
		int a, b;
		for (int i = 0; i < n; i++) {
			cin >> a >> b;
			a--, b--;
			green.insert({ a,b });
			green1.insert(a * c + b);
		}
		int t;
		cin >> t;
		while (t--) {
			int y1, x1, y2, x2;
			cin >> y1 >> x1 >> y2 >> x2;
			y1--, x1--, y2--, x2--;
			auto it = green1.lower_bound(y1 * c + x1);
			if (*it <= y1 * c + x2)
				cout << "YES";
			else
				cout << "NO";
			cout << endl;
		}
	}
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2892 KB 200 token(s): yes count is 21, no count is 179
2 Correct 33 ms 2440 KB 200 token(s): yes count is 70, no count is 130
3 Correct 23 ms 2796 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 358 ms 19028 KB expected NO, found YES [1st token]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 27.0

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