# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
836533 | 2023-08-24T12:28:18 Z | ma_moutahid | Keys (IOI21_keys) | C++17 | 3000 ms | 32376 KB |
#include <vector> #include<bits/stdc++.h> using namespace std; #define vi vector<int> #define vii vector<vi> #define pi pair<int,int> #define vp vector<pi> vector<vp> g; std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { int n=r.size(); g.resize(n); int m=u.size(); for(int i=0;i<m;i++){ g[u[i]].push_back(make_pair(c[i],v[i])); g[v[i]].push_back(make_pair(c[i],u[i])); } vi result(n); for(int root=0;root<n;root++){ vi traversed(n); traversed[root]=1; set<int>keys; keys.insert(r[root]); int nk=1; multimap<int,int>bridges; for(pi p:g[root]){ if(traversed[p.second])continue; bridges.insert(p); } while(nk){ nk=0; for(int key:keys){ auto itr=bridges.find(key); while(itr!=bridges.end()){ if(!traversed[itr->second]){ traversed[itr->second]=true; int old=keys.size(); keys.insert(r[itr->second]); if(old!=keys.size())nk++; result[root]++; for(pi p:g[itr->second]){ if(traversed[p.second])continue; bridges.insert(p); } } bridges.erase(itr); itr=bridges.find(key); } } } } int mn=*min_element(result.begin(),result.end()); for(int i=0;i<n;i++){ result[i]=(result[i]==mn); } return result; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 2 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 2 ms | 212 KB | Output is correct |
9 | Correct | 3 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 2 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 2 ms | 212 KB | Output is correct |
9 | Correct | 3 ms | 212 KB | Output is correct |
10 | Correct | 6 ms | 212 KB | Output is correct |
11 | Correct | 6 ms | 300 KB | Output is correct |
12 | Correct | 6 ms | 212 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 7 ms | 320 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 212 KB | Output is correct |
18 | Correct | 1 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 4 ms | 296 KB | Output is correct |
22 | Correct | 3 ms | 212 KB | Output is correct |
23 | Correct | 12 ms | 320 KB | Output is correct |
24 | Correct | 18 ms | 212 KB | Output is correct |
25 | Correct | 18 ms | 340 KB | Output is correct |
26 | Correct | 25 ms | 300 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 2 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 2 ms | 212 KB | Output is correct |
9 | Correct | 3 ms | 212 KB | Output is correct |
10 | Correct | 6 ms | 212 KB | Output is correct |
11 | Correct | 6 ms | 300 KB | Output is correct |
12 | Correct | 6 ms | 212 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 7 ms | 320 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 212 KB | Output is correct |
18 | Correct | 1 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 4 ms | 296 KB | Output is correct |
22 | Correct | 3 ms | 212 KB | Output is correct |
23 | Correct | 12 ms | 320 KB | Output is correct |
24 | Correct | 18 ms | 212 KB | Output is correct |
25 | Correct | 18 ms | 340 KB | Output is correct |
26 | Correct | 25 ms | 300 KB | Output is correct |
27 | Correct | 2907 ms | 616 KB | Output is correct |
28 | Correct | 2850 ms | 616 KB | Output is correct |
29 | Correct | 2909 ms | 612 KB | Output is correct |
30 | Correct | 353 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 2 ms | 340 KB | Output is correct |
33 | Correct | 2 ms | 340 KB | Output is correct |
34 | Correct | 100 ms | 408 KB | Output is correct |
35 | Correct | 748 ms | 424 KB | Output is correct |
36 | Execution timed out | 3066 ms | 568 KB | Time limit exceeded |
37 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 2 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 2 ms | 212 KB | Output is correct |
9 | Correct | 3 ms | 212 KB | Output is correct |
10 | Execution timed out | 3026 ms | 32376 KB | Time limit exceeded |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 2 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 2 ms | 212 KB | Output is correct |
9 | Correct | 3 ms | 212 KB | Output is correct |
10 | Correct | 6 ms | 212 KB | Output is correct |
11 | Correct | 6 ms | 300 KB | Output is correct |
12 | Correct | 6 ms | 212 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 0 ms | 212 KB | Output is correct |
15 | Correct | 7 ms | 320 KB | Output is correct |
16 | Correct | 1 ms | 212 KB | Output is correct |
17 | Correct | 1 ms | 212 KB | Output is correct |
18 | Correct | 1 ms | 212 KB | Output is correct |
19 | Correct | 1 ms | 212 KB | Output is correct |
20 | Correct | 1 ms | 212 KB | Output is correct |
21 | Correct | 4 ms | 296 KB | Output is correct |
22 | Correct | 3 ms | 212 KB | Output is correct |
23 | Correct | 12 ms | 320 KB | Output is correct |
24 | Correct | 18 ms | 212 KB | Output is correct |
25 | Correct | 18 ms | 340 KB | Output is correct |
26 | Correct | 25 ms | 300 KB | Output is correct |
27 | Correct | 2907 ms | 616 KB | Output is correct |
28 | Correct | 2850 ms | 616 KB | Output is correct |
29 | Correct | 2909 ms | 612 KB | Output is correct |
30 | Correct | 353 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 2 ms | 340 KB | Output is correct |
33 | Correct | 2 ms | 340 KB | Output is correct |
34 | Correct | 100 ms | 408 KB | Output is correct |
35 | Correct | 748 ms | 424 KB | Output is correct |
36 | Execution timed out | 3066 ms | 568 KB | Time limit exceeded |
37 | Halted | 0 ms | 0 KB | - |