# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
441787 | 2021-07-06T07:33:24 Z | alan8585 | Keys (IOI21_keys) | C++17 | 211 ms | 36076 KB |
#include <vector> #include <stack> using namespace std; const int MAXN = 300100; int T, in[MAXN], low[MAXN], instack[MAXN], bs[MAXN]; vector<int> e[MAXN]; stack<int> st; vector<vector<int>> SCC; vector<int> flags; void dfs(int a) { instack[a] = 1; st.push(a); in[a] = low[a] = ++T; for(int i : e[a]) { if(!in[i]) { dfs(i); low[a] = min(low[a], low[i]); } else if(instack[i]) { low[a] = min(low[a], in[i]); } } if(in[a] == low[a]) { int now = -1; SCC.push_back(vector<int>(0)); do { now = st.top(); st.pop(); SCC.back().push_back(now); bs[now] = SCC.size(); } while(now != a); } } std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { std::vector<int> ans(r.size(), 0); int n = r.size(), m = u.size(); for(int i = 0; i < m; i++) { if(r[u[i]] == c[i]) e[u[i]].push_back(v[i]); if(r[v[i]] == c[i]) e[v[i]].push_back(u[i]); } for(int i = 0; i < n; i++) { if(!in[i]) { dfs(i); } } int nmin = MAXN; for(int i = 0; i < (int)SCC.size(); i++) { int flag = 1; for(int j : SCC[i]) { for(int k : e[j]) { if(bs[k] != i + 1) flag = 0; } } flags.push_back(flag); if(flag) { nmin = min(nmin, (int)SCC[i].size()); } } for(int i = 0; i < (int)SCC.size(); i++) { if(flags[i] && SCC[i].size() == nmin) { for(int j : SCC[i]) ans[j] = 1; } } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7244 KB | Output is correct |
2 | Correct | 4 ms | 7244 KB | Output is correct |
3 | Correct | 4 ms | 7332 KB | Output is correct |
4 | Correct | 4 ms | 7372 KB | Output is correct |
5 | Correct | 4 ms | 7244 KB | Output is correct |
6 | Correct | 5 ms | 7336 KB | Output is correct |
7 | Correct | 4 ms | 7244 KB | Output is correct |
8 | Correct | 5 ms | 7316 KB | Output is correct |
9 | Correct | 5 ms | 7372 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7244 KB | Output is correct |
2 | Correct | 4 ms | 7244 KB | Output is correct |
3 | Correct | 4 ms | 7332 KB | Output is correct |
4 | Correct | 4 ms | 7372 KB | Output is correct |
5 | Correct | 4 ms | 7244 KB | Output is correct |
6 | Correct | 5 ms | 7336 KB | Output is correct |
7 | Correct | 4 ms | 7244 KB | Output is correct |
8 | Correct | 5 ms | 7316 KB | Output is correct |
9 | Correct | 5 ms | 7372 KB | Output is correct |
10 | Correct | 4 ms | 7372 KB | Output is correct |
11 | Correct | 4 ms | 7336 KB | Output is correct |
12 | Correct | 4 ms | 7372 KB | Output is correct |
13 | Correct | 4 ms | 7244 KB | Output is correct |
14 | Correct | 5 ms | 7244 KB | Output is correct |
15 | Correct | 5 ms | 7340 KB | Output is correct |
16 | Correct | 5 ms | 7244 KB | Output is correct |
17 | Incorrect | 5 ms | 7244 KB | Output isn't correct |
18 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7244 KB | Output is correct |
2 | Correct | 4 ms | 7244 KB | Output is correct |
3 | Correct | 4 ms | 7332 KB | Output is correct |
4 | Correct | 4 ms | 7372 KB | Output is correct |
5 | Correct | 4 ms | 7244 KB | Output is correct |
6 | Correct | 5 ms | 7336 KB | Output is correct |
7 | Correct | 4 ms | 7244 KB | Output is correct |
8 | Correct | 5 ms | 7316 KB | Output is correct |
9 | Correct | 5 ms | 7372 KB | Output is correct |
10 | Correct | 4 ms | 7372 KB | Output is correct |
11 | Correct | 4 ms | 7336 KB | Output is correct |
12 | Correct | 4 ms | 7372 KB | Output is correct |
13 | Correct | 4 ms | 7244 KB | Output is correct |
14 | Correct | 5 ms | 7244 KB | Output is correct |
15 | Correct | 5 ms | 7340 KB | Output is correct |
16 | Correct | 5 ms | 7244 KB | Output is correct |
17 | Incorrect | 5 ms | 7244 KB | Output isn't correct |
18 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7244 KB | Output is correct |
2 | Correct | 4 ms | 7244 KB | Output is correct |
3 | Correct | 4 ms | 7332 KB | Output is correct |
4 | Correct | 4 ms | 7372 KB | Output is correct |
5 | Correct | 4 ms | 7244 KB | Output is correct |
6 | Correct | 5 ms | 7336 KB | Output is correct |
7 | Correct | 4 ms | 7244 KB | Output is correct |
8 | Correct | 5 ms | 7316 KB | Output is correct |
9 | Correct | 5 ms | 7372 KB | Output is correct |
10 | Correct | 139 ms | 30328 KB | Output is correct |
11 | Incorrect | 211 ms | 36076 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7244 KB | Output is correct |
2 | Correct | 4 ms | 7244 KB | Output is correct |
3 | Correct | 4 ms | 7332 KB | Output is correct |
4 | Correct | 4 ms | 7372 KB | Output is correct |
5 | Correct | 4 ms | 7244 KB | Output is correct |
6 | Correct | 5 ms | 7336 KB | Output is correct |
7 | Correct | 4 ms | 7244 KB | Output is correct |
8 | Correct | 5 ms | 7316 KB | Output is correct |
9 | Correct | 5 ms | 7372 KB | Output is correct |
10 | Correct | 4 ms | 7372 KB | Output is correct |
11 | Correct | 4 ms | 7336 KB | Output is correct |
12 | Correct | 4 ms | 7372 KB | Output is correct |
13 | Correct | 4 ms | 7244 KB | Output is correct |
14 | Correct | 5 ms | 7244 KB | Output is correct |
15 | Correct | 5 ms | 7340 KB | Output is correct |
16 | Correct | 5 ms | 7244 KB | Output is correct |
17 | Incorrect | 5 ms | 7244 KB | Output isn't correct |
18 | Halted | 0 ms | 0 KB | - |