# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
974560 | 2024-05-03T13:07:10 Z | onlk97 | Keys (IOI21_keys) | C++17 | 178 ms | 61420 KB |
#include <vector> #include <bits/stdc++.h> using namespace std; vector <int> in[300010],out[300010]; bool visited[300010]; stack <int> st; void dfs1(int cur){ visited[cur]=1; for (int i:out[cur]){ if (!visited[i]) dfs1(i); } st.push(cur); } vector <vector <int> > scc; int belong[300010],idx; vector <int> cc; void dfs2(int cur){ cc.push_back(cur); belong[cur]=idx; visited[cur]=1; for (int i:in[cur]){ if (!visited[i]) dfs2(i); } } vector <int> find_reachable(vector <int> r,vector <int> u,vector <int> v,vector <int> c){ int n=r.size(),m=u.size(); for (int i=0; i<m; i++){ if (r[u[i]]==c[i]){ out[u[i]].push_back(v[i]); in[v[i]].push_back(u[i]); } if (r[v[i]]==c[i]){ out[v[i]].push_back(u[i]); in[u[i]].push_back(v[i]); } } for (int i=0; i<n; i++){ if (!visited[i]) dfs1(i); } for (int i=0; i<n; i++) visited[i]=0; while (!st.empty()){ int tp=st.top(); st.pop(); if (visited[tp]) continue; dfs2(tp); scc.push_back(cc); idx++; cc.clear(); } vector <int> safe; for (int i=0; i<n; i++){ int ok=1; for (int j:out[i]){ if (belong[i]!=belong[j]) ok=0; } safe.push_back(ok); } int mn=1e9; for (auto i:scc){ bool ok=1; for (int j:i){ if (!safe[j]) ok=0; } if (ok) mn=min(mn,(int)i.size()); } vector <int> ans(n,0); for (auto i:scc){ bool ok=1; for (int j:i){ if (!safe[j]) ok=0; } if (ok&&i.size()==mn){ for (int j:i) ans[j]=1; } } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 15708 KB | Output is correct |
2 | Correct | 5 ms | 15708 KB | Output is correct |
3 | Correct | 4 ms | 15708 KB | Output is correct |
4 | Correct | 3 ms | 15808 KB | Output is correct |
5 | Correct | 3 ms | 15708 KB | Output is correct |
6 | Correct | 4 ms | 15708 KB | Output is correct |
7 | Correct | 5 ms | 15708 KB | Output is correct |
8 | Correct | 4 ms | 15844 KB | Output is correct |
9 | Correct | 4 ms | 15824 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 15708 KB | Output is correct |
2 | Correct | 5 ms | 15708 KB | Output is correct |
3 | Correct | 4 ms | 15708 KB | Output is correct |
4 | Correct | 3 ms | 15808 KB | Output is correct |
5 | Correct | 3 ms | 15708 KB | Output is correct |
6 | Correct | 4 ms | 15708 KB | Output is correct |
7 | Correct | 5 ms | 15708 KB | Output is correct |
8 | Correct | 4 ms | 15844 KB | Output is correct |
9 | Correct | 4 ms | 15824 KB | Output is correct |
10 | Correct | 4 ms | 15704 KB | Output is correct |
11 | Correct | 4 ms | 15704 KB | Output is correct |
12 | Correct | 4 ms | 15796 KB | Output is correct |
13 | Correct | 4 ms | 15816 KB | Output is correct |
14 | Correct | 4 ms | 15708 KB | Output is correct |
15 | Correct | 4 ms | 15704 KB | Output is correct |
16 | Correct | 4 ms | 15708 KB | Output is correct |
17 | Incorrect | 3 ms | 15708 KB | Output isn't correct |
18 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 15708 KB | Output is correct |
2 | Correct | 5 ms | 15708 KB | Output is correct |
3 | Correct | 4 ms | 15708 KB | Output is correct |
4 | Correct | 3 ms | 15808 KB | Output is correct |
5 | Correct | 3 ms | 15708 KB | Output is correct |
6 | Correct | 4 ms | 15708 KB | Output is correct |
7 | Correct | 5 ms | 15708 KB | Output is correct |
8 | Correct | 4 ms | 15844 KB | Output is correct |
9 | Correct | 4 ms | 15824 KB | Output is correct |
10 | Correct | 4 ms | 15704 KB | Output is correct |
11 | Correct | 4 ms | 15704 KB | Output is correct |
12 | Correct | 4 ms | 15796 KB | Output is correct |
13 | Correct | 4 ms | 15816 KB | Output is correct |
14 | Correct | 4 ms | 15708 KB | Output is correct |
15 | Correct | 4 ms | 15704 KB | Output is correct |
16 | Correct | 4 ms | 15708 KB | Output is correct |
17 | Incorrect | 3 ms | 15708 KB | Output isn't correct |
18 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 15708 KB | Output is correct |
2 | Correct | 5 ms | 15708 KB | Output is correct |
3 | Correct | 4 ms | 15708 KB | Output is correct |
4 | Correct | 3 ms | 15808 KB | Output is correct |
5 | Correct | 3 ms | 15708 KB | Output is correct |
6 | Correct | 4 ms | 15708 KB | Output is correct |
7 | Correct | 5 ms | 15708 KB | Output is correct |
8 | Correct | 4 ms | 15844 KB | Output is correct |
9 | Correct | 4 ms | 15824 KB | Output is correct |
10 | Correct | 113 ms | 40756 KB | Output is correct |
11 | Incorrect | 178 ms | 61420 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 15708 KB | Output is correct |
2 | Correct | 5 ms | 15708 KB | Output is correct |
3 | Correct | 4 ms | 15708 KB | Output is correct |
4 | Correct | 3 ms | 15808 KB | Output is correct |
5 | Correct | 3 ms | 15708 KB | Output is correct |
6 | Correct | 4 ms | 15708 KB | Output is correct |
7 | Correct | 5 ms | 15708 KB | Output is correct |
8 | Correct | 4 ms | 15844 KB | Output is correct |
9 | Correct | 4 ms | 15824 KB | Output is correct |
10 | Correct | 4 ms | 15704 KB | Output is correct |
11 | Correct | 4 ms | 15704 KB | Output is correct |
12 | Correct | 4 ms | 15796 KB | Output is correct |
13 | Correct | 4 ms | 15816 KB | Output is correct |
14 | Correct | 4 ms | 15708 KB | Output is correct |
15 | Correct | 4 ms | 15704 KB | Output is correct |
16 | Correct | 4 ms | 15708 KB | Output is correct |
17 | Incorrect | 3 ms | 15708 KB | Output isn't correct |
18 | Halted | 0 ms | 0 KB | - |