Submission #658861

#	Time	Username	Problem	Language	Result	Execution time	Memory
658861		Foxyy	Kutije (COCI21_kutije)	C++17	35 / 70	1081 ms	18064 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define Foxyy cin.tie(0); cout.sync_with_stdio(0); cout.tie(0);
 
struct Solver {
	int& n;
	int& m;
	int& q;
	vector<vector<int>>& p;
	
	vector<vector<int>> adj{};
	
	void getAdj() {
		adj.resize(n);
		for (auto& vec : p) {
			for (int i = 0; i < n; i++) {
				adj[vec[i]].push_back(i);
			}
		}
	}
	
	vector<bool> getReachableState(int x) {
		queue<int> q;
		q.push(x);
		vector<bool> vst(n);
		while (not q.empty()) {
			int u = q.front();
			q.pop();
			
			if (vst[u]) continue;
			vst[u] = true;
			
			for (auto v : adj[u]) {
				q.push(v);
			}
		}
		return vst;
	}
	
	void solve() {
		getAdj();
		vector<vector<bool>> reachable(n);
		for (int i = 0; i < n; i++) {
			reachable[i] = getReachableState(i);
		}
		
		for (int _ = 0; _ < q; _++) {
			int a, b;
			cin >> a >> b;
			a--, b--;
			if (reachable[a][b]) {
				cout << "DA\n";
			} else {
				cout << "NE\n";
			}
		}
	}
};
 
signed main() {
	Foxyy
	
	int T = 1;
//	cin >> T;
	while(T--) {
		int n, m, q;
		cin >> n >> m >> q;
		vector<vector<int>> p(m, vector<int>(n));
		for (auto& vec : p) {
			for (auto& x : vec) {
				cin >> x;
				x--;
			}
		}
		
		Solver solver{n, m, q, p};
		solver.solve();
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 35