#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define debug(x) cerr << #x << " is " << x << endl
#define el '\n'
using namespace std; using ll = long long;
const int N = 1003, Q = 500003;
struct DSU {
vector<int> par, sz;
DSU(int n): par(n+1), sz(n+1,1) {iota(par.begin(),par.end(),0);}
int find(int x) {
if (x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
if (sz[a] > sz[b]) swap(a,b);
sz[b] += sz[a];
par[a] = b;
}
int size(int x) {return sz[find(x)];}
bool same(int a, int b) {return find(a) == find(b);}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, m, q; cin >> n >> m >> q;
// n: the number of boxes
// m: the number of friends
// q: the number of questions
DSU toys(n);
int p[N] = {0,};
REP(k,1,m) {
REP(i,1,n) {
cin >> p[i];
// k번째 친구가 사용할
// 장난감 도로 넣을 박스들
toys.merge(i,p[i]);
}
}
REP(i,1,q) {
int a, b; cin >> a >> b;
cout << (toys.same(a,b) ? "DA" : "NE") << el;
}
// if it's possible: DA
// else: NE
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
5592 KB |
Output is correct |
| 2 |
Correct |
75 ms |
4868 KB |
Output is correct |
| 3 |
Correct |
82 ms |
4620 KB |
Output is correct |
| 4 |
Correct |
80 ms |
5528 KB |
Output is correct |
| 5 |
Correct |
97 ms |
5556 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
312 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
308 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
324 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
312 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
308 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
2 ms |
324 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
2 ms |
332 KB |
Output is correct |
| 12 |
Correct |
2 ms |
336 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
2 ms |
328 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
324 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
324 KB |
Output is correct |
| 20 |
Correct |
1 ms |
328 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
5592 KB |
Output is correct |
| 2 |
Correct |
75 ms |
4868 KB |
Output is correct |
| 3 |
Correct |
82 ms |
4620 KB |
Output is correct |
| 4 |
Correct |
80 ms |
5528 KB |
Output is correct |
| 5 |
Correct |
97 ms |
5556 KB |
Output is correct |
| 6 |
Correct |
1 ms |
312 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
308 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
324 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
2 ms |
324 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
2 ms |
332 KB |
Output is correct |
| 17 |
Correct |
2 ms |
336 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
2 ms |
328 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
324 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
324 KB |
Output is correct |
| 25 |
Correct |
1 ms |
328 KB |
Output is correct |
| 26 |
Correct |
154 ms |
9400 KB |
Output is correct |
| 27 |
Correct |
149 ms |
9520 KB |
Output is correct |
| 28 |
Correct |
131 ms |
7816 KB |
Output is correct |
| 29 |
Correct |
138 ms |
9132 KB |
Output is correct |
| 30 |
Correct |
147 ms |
8064 KB |
Output is correct |
| 31 |
Correct |
139 ms |
7964 KB |
Output is correct |
| 32 |
Correct |
143 ms |
9504 KB |
Output is correct |
| 33 |
Correct |
151 ms |
9372 KB |
Output is correct |
| 34 |
Correct |
157 ms |
9324 KB |
Output is correct |
| 35 |
Correct |
147 ms |
9372 KB |
Output is correct |
