답안 #658861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658861	2022-11-15T07:52:10 Z	Foxyy	Kutije (COCI21_kutije)	C++17	35 / 70	1000 ms	18064 KB

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.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	5900 KB	Output is correct
2	Correct	94 ms	5108 KB	Output is correct
3	Correct	92 ms	4832 KB	Output is correct
4	Correct	85 ms	5876 KB	Output is correct
5	Correct	81 ms	5816 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	5 ms	468 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	5 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	456 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	5 ms	468 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	5 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	456 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	2 ms	396 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	7 ms	456 KB	Output is correct
14	Correct	3 ms	340 KB	Output is correct
15	Correct	2 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	5 ms	468 KB	Output is correct
18	Correct	1 ms	460 KB	Output is correct
19	Correct	2 ms	468 KB	Output is correct
20	Correct	2 ms	456 KB	Output is correct

Subtask #4

0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	5900 KB	Output is correct
2	Correct	94 ms	5108 KB	Output is correct
3	Correct	92 ms	4832 KB	Output is correct
4	Correct	85 ms	5876 KB	Output is correct
5	Correct	81 ms	5816 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	5 ms	468 KB	Output is correct
9	Correct	3 ms	468 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	2 ms	468 KB	Output is correct
12	Correct	5 ms	468 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	456 KB	Output is correct
15	Correct	2 ms	468 KB	Output is correct
16	Correct	2 ms	396 KB	Output is correct
17	Correct	2 ms	468 KB	Output is correct
18	Correct	7 ms	456 KB	Output is correct
19	Correct	3 ms	340 KB	Output is correct
20	Correct	2 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	5 ms	468 KB	Output is correct
23	Correct	1 ms	460 KB	Output is correct
24	Correct	2 ms	468 KB	Output is correct
25	Correct	2 ms	456 KB	Output is correct
26	Correct	600 ms	18064 KB	Output is correct
27	Correct	193 ms	17896 KB	Output is correct
28	Execution timed out	1081 ms	14248 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-