Submission #658864

#	Time	Username	Problem	Language	Result	Execution time	Memory
658864		Foxyy	Kutije (COCI21_kutije)	C++17	70 / 70	218 ms	17544 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{};
	vector<int> scc{};
	int sccCnt = 0;
	vector<vector<int>> sccAdj{};
	vector<set<int>> reachable{};
	
	void getAdj() {
		adj.resize(n);
		for (auto& vec : p) {
			for (int i = 0; i < n; i++) if (i != vec[i]) {
				adj[vec[i]].push_back(i);
			}
		}
		for (int i = 0; i < n; i++) {
			sort(adj[i].begin(), adj[i].end());
			adj[i].resize(unique(adj[i].begin(), adj[i].end()) - adj[i].begin());
		}
	}
	
	void getSCC() {
		vector<int> dep(n), low(n);
		stack<int, vector<int>> stk;
		vector<bool> inStk(n);
		int ts = 0;
		scc.resize(n);
		
		function<void(int)> dfs = [&](int u) {
//			cerr << "Entering dfs(" << u << ")...\n";
			dep[u] = low[u] = ++ts;
			stk.push(u);
			inStk[u] = true;
			
			for (int v : adj[u]) {
				if (not dep[v]) {
					dfs(v);
				}
				if (inStk[v]) {
					low[u] = min(low[u], low[v]);
				}
			}
			
//			cerr << "low[" << u << "] = " << low[u] << ", dep[" << u << "] = " << dep[u] << '\n';
						
			if (low[u] == dep[u]) {
				while (true) {
					int x = stk.top();
					stk.pop();
					inStk[x] = false;
					scc[x] = sccCnt;
					if (x == u) {
						break;
					}
				}
				sccCnt++;
			}
			
//			cerr << "Exiting from dfs(" << u << ")...\n";
		};
		
		for (int i = 0; i < n; i++) {
			if (not dep[i]) {
//				cerr << "Calling dfs(" << i << ")...\n";
				dfs(i);
			}
		}
	}
	
	void getSCCAdj() {
		sccAdj.resize(sccCnt);
		for (int i = 0; i < n; i++) {
			for (int j : adj[i]) {
				if (scc[i] != scc[j]) {
					adj[scc[i]].push_back(scc[j]);
				}
			}
		}
	}
	
	void getReachable() {
		reachable.resize(sccCnt);
		for (int i = 0; i < sccCnt; i++) {
			reachable[i].insert(i);
			for (int j : sccAdj[i]) {
				for (int x : reachable[j]) {
					reachable[i].insert(x);
				}
			}
		}
	}
	
	void solve() {
//		cerr << "Calling getAdj()...\n";
		getAdj();
//		cerr << "Calling getSCC()...\n";
		getSCC();
//		cerr << "sccCnt = " << sccCnt << '\n';
//		cerr << "Calling getSCCAdj()...\n";
		getSCCAdj();
//		cerr << "Calling getReachable()...\n";
		getReachable();
		
		for (int _ = 0; _ < q; _++) {
			int a, b;
			cin >> a >> b;
			a--, b--;
			if (reachable[scc[a]].find(scc[b]) != reachable[scc[a]].end()) {
				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: 35 / 35