# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
781042 |
2023-07-12T16:20:35 Z |
cig32 |
Kutije (COCI21_kutije) |
C++17 |
|
147 ms |
26052 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1001;
vector<int> adj[MAXN], adj2[MAXN], adj3[MAXN];
bool vis[MAXN];
stack<int> topolo;
void dfs1(int node) {
vis[node] = 1;
for(int x: adj[node]) {
if(!vis[x]) dfs1(x);
}
topolo.push(node);
}
vector<vector<int> > components;
vector<int> wow;
void dfs2(int node) {
vis[node] = 1;
for(int x : adj2[node]) {
if(!vis[x]) dfs2(x);
}
wow.push_back(node);
}
void dfs3(int node) {
vis[node] = 1;
for(int x : adj3[node]) {
if(!vis[x]) dfs3(x);
}
topolo.push(node);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m, q; cin >> n >> m >> q;
int ans[n+1][n+1];
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
ans[i][j] = 0;
}
}
for(int i=1; i<=m; i++) {
for(int j=1; j<=n; j++) {
int x; cin >> x;
adj[x].push_back(j);
adj2[j].push_back(x);
}
}
for(int i=1; i<=n; i++) {
if(!vis[i]) {
dfs1(i);
}
}
for(int i=1; i<=n; i++) {
vis[i] = 0;
}
int dage[n+1];
while(topolo.size()) {
if(!vis[topolo.top()]){
vis[topolo.top()]=1;
wow.clear();
dfs2(topolo.top());
for(int x : wow) {
for(int y : wow) {
ans[x][y] = 1;
}
}
for(int x : wow) {
dage[x] = wow[0];
}
components.push_back(wow);
}
topolo.pop();
}
int done[n+1][n+1];
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
done[i][j] = 0;
}
}
for(int i=1; i<=n; i++) {
for(int x : adj[i]) {
if(dage[i] != dage[x] && done[dage[i]][dage[x]] == 0) {
adj3[dage[i]].push_back(dage[x]);
done[dage[i]][dage[x]] = 1;
}
}
}
while(q--) {
int a, b; cin >> a >> b;
cout << (ans[a][b]? "DA\n":"NE\n");
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
13580 KB |
Output is correct |
2 |
Correct |
58 ms |
11852 KB |
Output is correct |
3 |
Correct |
55 ms |
11212 KB |
Output is correct |
4 |
Correct |
70 ms |
13548 KB |
Output is correct |
5 |
Correct |
64 ms |
13616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
520 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
532 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
532 KB |
Output is correct |
9 |
Correct |
1 ms |
520 KB |
Output is correct |
10 |
Correct |
1 ms |
516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
520 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
532 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
532 KB |
Output is correct |
9 |
Correct |
1 ms |
520 KB |
Output is correct |
10 |
Correct |
1 ms |
516 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
504 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
532 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
13580 KB |
Output is correct |
2 |
Correct |
58 ms |
11852 KB |
Output is correct |
3 |
Correct |
55 ms |
11212 KB |
Output is correct |
4 |
Correct |
70 ms |
13548 KB |
Output is correct |
5 |
Correct |
64 ms |
13616 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
520 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
532 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
532 KB |
Output is correct |
14 |
Correct |
1 ms |
520 KB |
Output is correct |
15 |
Correct |
1 ms |
516 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
504 KB |
Output is correct |
20 |
Correct |
1 ms |
596 KB |
Output is correct |
21 |
Correct |
1 ms |
596 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
1 ms |
532 KB |
Output is correct |
24 |
Correct |
1 ms |
596 KB |
Output is correct |
25 |
Correct |
1 ms |
596 KB |
Output is correct |
26 |
Correct |
126 ms |
26012 KB |
Output is correct |
27 |
Correct |
147 ms |
26052 KB |
Output is correct |
28 |
Correct |
116 ms |
22348 KB |
Output is correct |
29 |
Correct |
128 ms |
25348 KB |
Output is correct |
30 |
Correct |
109 ms |
22008 KB |
Output is correct |
31 |
Correct |
109 ms |
22348 KB |
Output is correct |
32 |
Correct |
124 ms |
25568 KB |
Output is correct |
33 |
Correct |
127 ms |
25420 KB |
Output is correct |
34 |
Correct |
147 ms |
25412 KB |
Output is correct |
35 |
Correct |
125 ms |
25864 KB |
Output is correct |