Submission #487923

#	Time	Username	Problem	Language	Result	Execution time	Memory
487923		maks007	Trampoline (info1cup20_trampoline)	C++14	0 / 100	722 ms	465116 KiB

trampoline

#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];
	vector <int> in(N), out(N);

	int time = 0;

	function <void(int)> dfs=[&](int v) {
		used[v] = 1;
		in[v] = time ++;
		for(int i = 0; i < g[v].size(); i ++) {
			if(!used[g[v][i]]) dfs(g[v][i]);
		}
		out[v] = time ++;
	};

	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);
		 }
	}

	for(int i = 0; i < N; i ++) if(!used[i]) dfs(i);
	int q;

	cin >> q;
	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 --;
		if(in[mp[start.first][start.second].first] < in[mp[end.first][end.second].first] 
		and out[mp[start.first][start.second].first] > out[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 (stderr)

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

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