oj.uz

Submission #487911

# Submission time Handle Problem Language Result Execution time Memory
487911 2021-11-17T03:12:57 Z maks007 Trampoline (info1cup20_trampoline) C++14
23 / 100
 2000 ms 416052 KB 
#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n, m, green;
	cin >> n >> m >> green;
	const int N = n * m;
	vector <int> used(N);
	vector <vector <int>> g(N);
	pair <int, int> mp[n][m];

	int cnt = 0;

	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) {
			mp[i][j].first = cnt ++;
			mp[i][j].second = 0;
		}
	} 

	for(int i = 0; i < green; i ++) {
		int x, y;
		cin >> x >> y;
 		x --;
 		y --;
 		mp[x][y].second = 1;
	}

	for(int i = 0; i < n; i ++) {
		 for(int j = 0; j < m; j ++) {
		 	if(j != m - 1)
		 	g[mp[i][j].first].push_back(mp[i][j+1].first);
		 	if(i != n - 1)
		 	if(mp[i][j].second == 1) g[mp[i][j].first].push_back(mp[i+1][j].first);
		 }
	}
	int q;
	cin >> q;
	queue <int> order;
	while(q --) {
		pair <int, int> start, end;
		cin >> start.first >> start.second;
		cin >> end.first >> end.second;
		end.first --;
		end.second --;
		start.first --;
		start.second --;
		for(int i = 0; i < used.size(); i ++) used[i] = 0;
		order.push(mp[start.first][start.second].first);
		used[mp[start.first][start.second].first] = 1;
		while(!order.empty()) {
			int v = order.front();
			order.pop();
			for(int i = 0; i < g[v].size(); i ++) {
				if(!used[g[v][i]]) {
					order.push(g[v][i]);
					used[g[v][i]] = 1;
				}
			}
		}
		if(used[mp[end.first][end.second].first]) cout << "Yes\n";
		else cout << "No\n";
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int Q = 1;
	//cin >> Q;
	while (Q --) {
		solve();
	}
	return 0;
}

Compilation message

trampoline.cpp: In function 'void solve()':
trampoline.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i = 0; i < used.size(); i ++) used[i] = 0;
      |                  ~~^~~~~~~~~~~~~
trampoline.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for(int i = 0; i < g[v].size(); i ++) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2892 KB 200 token(s): yes count is 21, no count is 179
2 Correct 23 ms 2252 KB 200 token(s): yes count is 70, no count is 130
3 Correct 11 ms 2892 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2100 ms 416052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -