# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
835752 | 2023-08-23T19:16:14 Z | JakobZorz | Keys (IOI21_keys) | C++17 | 2241 ms | 67960 KB |
#include"keys.h" #include<iostream> #include<vector> #include<unordered_set> #include<unordered_map> #include<queue> using namespace std; typedef long long ll; int res[300000]; int key[300000]; bool done[300000]; vector<pair<int,int>>nodes[300000]; int min_res=1e6; int n,m; void search(int x){ unordered_set<int>keys,visited; unordered_map<int,vector<int>>blocked; queue<int>q; visited.insert(x); q.push(x); while(!q.empty()){ if(visited.size()>min_res) return; int node=q.front(); q.pop(); if(done[node]) return; if(keys.find(key[node])==keys.end()){ keys.insert(key[node]); for(int node2:blocked[key[node]]){ if(visited.find(node2)==visited.end()){ visited.insert(node2); q.push(node2); } } } for(auto ne:nodes[node]){ if(keys.find(ne.second)==keys.end()){ blocked[ne.second].push_back(ne.first); }else{ if(visited.find(ne.first)==visited.end()){ visited.insert(ne.first); q.push(ne.first); } } } } for(int i:visited) res[i]=min(res[i],(int)visited.size()); } vector<int>find_reachable(vector<int>r,vector<int>u,vector<int>v,vector<int>c){ n=(int)r.size(); m=(int)c.size(); for(int i=0;i<n;i++){ key[i]=r[i]; res[i]=1e6; } vector<int>nd; for(int i=0;i<m;i++){ nodes[u[i]].push_back({v[i],c[i]}); nodes[v[i]].push_back({u[i],c[i]}); nd.push_back(u[i]); nd.push_back(v[i]); } for(int i=0;i<2*m;i++){ swap(nd[i],nd[rand()%(2*m)]); } for(int i:nd){ if(!done[i]){ search(i); min_res=min(min_res,res[i]); done[i]=true; } } for(int i=0;i<n;i++){ if(!done[i]){ search(i); min_res=min(min_res,res[i]); done[i]=true; } } vector<int>ans(n); for(int i=0;i<n;i++) ans[i]=res[i]==min_res; return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7360 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
3 | Correct | 3 ms | 7252 KB | Output is correct |
4 | Correct | 3 ms | 7276 KB | Output is correct |
5 | Correct | 3 ms | 7252 KB | Output is correct |
6 | Correct | 3 ms | 7252 KB | Output is correct |
7 | Correct | 5 ms | 7252 KB | Output is correct |
8 | Correct | 4 ms | 7380 KB | Output is correct |
9 | Correct | 3 ms | 7380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7360 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
3 | Correct | 3 ms | 7252 KB | Output is correct |
4 | Correct | 3 ms | 7276 KB | Output is correct |
5 | Correct | 3 ms | 7252 KB | Output is correct |
6 | Correct | 3 ms | 7252 KB | Output is correct |
7 | Correct | 5 ms | 7252 KB | Output is correct |
8 | Correct | 4 ms | 7380 KB | Output is correct |
9 | Correct | 3 ms | 7380 KB | Output is correct |
10 | Correct | 4 ms | 7380 KB | Output is correct |
11 | Correct | 4 ms | 7380 KB | Output is correct |
12 | Correct | 3 ms | 7380 KB | Output is correct |
13 | Correct | 3 ms | 7252 KB | Output is correct |
14 | Correct | 3 ms | 7252 KB | Output is correct |
15 | Correct | 4 ms | 7380 KB | Output is correct |
16 | Correct | 3 ms | 7252 KB | Output is correct |
17 | Correct | 3 ms | 7252 KB | Output is correct |
18 | Correct | 3 ms | 7252 KB | Output is correct |
19 | Correct | 3 ms | 7252 KB | Output is correct |
20 | Correct | 3 ms | 7252 KB | Output is correct |
21 | Correct | 3 ms | 7380 KB | Output is correct |
22 | Correct | 3 ms | 7380 KB | Output is correct |
23 | Correct | 4 ms | 7380 KB | Output is correct |
24 | Correct | 3 ms | 7380 KB | Output is correct |
25 | Correct | 3 ms | 7380 KB | Output is correct |
26 | Correct | 4 ms | 7400 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7360 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
3 | Correct | 3 ms | 7252 KB | Output is correct |
4 | Correct | 3 ms | 7276 KB | Output is correct |
5 | Correct | 3 ms | 7252 KB | Output is correct |
6 | Correct | 3 ms | 7252 KB | Output is correct |
7 | Correct | 5 ms | 7252 KB | Output is correct |
8 | Correct | 4 ms | 7380 KB | Output is correct |
9 | Correct | 3 ms | 7380 KB | Output is correct |
10 | Correct | 4 ms | 7380 KB | Output is correct |
11 | Correct | 4 ms | 7380 KB | Output is correct |
12 | Correct | 3 ms | 7380 KB | Output is correct |
13 | Correct | 3 ms | 7252 KB | Output is correct |
14 | Correct | 3 ms | 7252 KB | Output is correct |
15 | Correct | 4 ms | 7380 KB | Output is correct |
16 | Correct | 3 ms | 7252 KB | Output is correct |
17 | Correct | 3 ms | 7252 KB | Output is correct |
18 | Correct | 3 ms | 7252 KB | Output is correct |
19 | Correct | 3 ms | 7252 KB | Output is correct |
20 | Correct | 3 ms | 7252 KB | Output is correct |
21 | Correct | 3 ms | 7380 KB | Output is correct |
22 | Correct | 3 ms | 7380 KB | Output is correct |
23 | Correct | 4 ms | 7380 KB | Output is correct |
24 | Correct | 3 ms | 7380 KB | Output is correct |
25 | Correct | 3 ms | 7380 KB | Output is correct |
26 | Correct | 4 ms | 7400 KB | Output is correct |
27 | Correct | 9 ms | 7840 KB | Output is correct |
28 | Correct | 6 ms | 7764 KB | Output is correct |
29 | Correct | 5 ms | 7508 KB | Output is correct |
30 | Correct | 6 ms | 7508 KB | Output is correct |
31 | Correct | 4 ms | 7508 KB | Output is correct |
32 | Correct | 4 ms | 7380 KB | Output is correct |
33 | Correct | 4 ms | 7380 KB | Output is correct |
34 | Correct | 5 ms | 7508 KB | Output is correct |
35 | Correct | 5 ms | 7508 KB | Output is correct |
36 | Correct | 8 ms | 7636 KB | Output is correct |
37 | Correct | 10 ms | 7708 KB | Output is correct |
38 | Correct | 9 ms | 7660 KB | Output is correct |
39 | Correct | 8 ms | 7784 KB | Output is correct |
40 | Correct | 5 ms | 7380 KB | Output is correct |
41 | Correct | 5 ms | 7400 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7360 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
3 | Correct | 3 ms | 7252 KB | Output is correct |
4 | Correct | 3 ms | 7276 KB | Output is correct |
5 | Correct | 3 ms | 7252 KB | Output is correct |
6 | Correct | 3 ms | 7252 KB | Output is correct |
7 | Correct | 5 ms | 7252 KB | Output is correct |
8 | Correct | 4 ms | 7380 KB | Output is correct |
9 | Correct | 3 ms | 7380 KB | Output is correct |
10 | Correct | 280 ms | 30376 KB | Output is correct |
11 | Correct | 399 ms | 44900 KB | Output is correct |
12 | Correct | 65 ms | 12352 KB | Output is correct |
13 | Correct | 395 ms | 30972 KB | Output is correct |
14 | Correct | 634 ms | 45236 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7360 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
3 | Correct | 3 ms | 7252 KB | Output is correct |
4 | Correct | 3 ms | 7276 KB | Output is correct |
5 | Correct | 3 ms | 7252 KB | Output is correct |
6 | Correct | 3 ms | 7252 KB | Output is correct |
7 | Correct | 5 ms | 7252 KB | Output is correct |
8 | Correct | 4 ms | 7380 KB | Output is correct |
9 | Correct | 3 ms | 7380 KB | Output is correct |
10 | Correct | 4 ms | 7380 KB | Output is correct |
11 | Correct | 4 ms | 7380 KB | Output is correct |
12 | Correct | 3 ms | 7380 KB | Output is correct |
13 | Correct | 3 ms | 7252 KB | Output is correct |
14 | Correct | 3 ms | 7252 KB | Output is correct |
15 | Correct | 4 ms | 7380 KB | Output is correct |
16 | Correct | 3 ms | 7252 KB | Output is correct |
17 | Correct | 3 ms | 7252 KB | Output is correct |
18 | Correct | 3 ms | 7252 KB | Output is correct |
19 | Correct | 3 ms | 7252 KB | Output is correct |
20 | Correct | 3 ms | 7252 KB | Output is correct |
21 | Correct | 3 ms | 7380 KB | Output is correct |
22 | Correct | 3 ms | 7380 KB | Output is correct |
23 | Correct | 4 ms | 7380 KB | Output is correct |
24 | Correct | 3 ms | 7380 KB | Output is correct |
25 | Correct | 3 ms | 7380 KB | Output is correct |
26 | Correct | 4 ms | 7400 KB | Output is correct |
27 | Correct | 9 ms | 7840 KB | Output is correct |
28 | Correct | 6 ms | 7764 KB | Output is correct |
29 | Correct | 5 ms | 7508 KB | Output is correct |
30 | Correct | 6 ms | 7508 KB | Output is correct |
31 | Correct | 4 ms | 7508 KB | Output is correct |
32 | Correct | 4 ms | 7380 KB | Output is correct |
33 | Correct | 4 ms | 7380 KB | Output is correct |
34 | Correct | 5 ms | 7508 KB | Output is correct |
35 | Correct | 5 ms | 7508 KB | Output is correct |
36 | Correct | 8 ms | 7636 KB | Output is correct |
37 | Correct | 10 ms | 7708 KB | Output is correct |
38 | Correct | 9 ms | 7660 KB | Output is correct |
39 | Correct | 8 ms | 7784 KB | Output is correct |
40 | Correct | 5 ms | 7380 KB | Output is correct |
41 | Correct | 5 ms | 7400 KB | Output is correct |
42 | Correct | 280 ms | 30376 KB | Output is correct |
43 | Correct | 399 ms | 44900 KB | Output is correct |
44 | Correct | 65 ms | 12352 KB | Output is correct |
45 | Correct | 395 ms | 30972 KB | Output is correct |
46 | Correct | 634 ms | 45236 KB | Output is correct |
47 | Correct | 3 ms | 7240 KB | Output is correct |
48 | Correct | 3 ms | 7252 KB | Output is correct |
49 | Correct | 3 ms | 7252 KB | Output is correct |
50 | Correct | 468 ms | 44680 KB | Output is correct |
51 | Correct | 529 ms | 43508 KB | Output is correct |
52 | Correct | 306 ms | 26344 KB | Output is correct |
53 | Correct | 255 ms | 26344 KB | Output is correct |
54 | Correct | 348 ms | 37180 KB | Output is correct |
55 | Correct | 285 ms | 36020 KB | Output is correct |
56 | Correct | 432 ms | 34556 KB | Output is correct |
57 | Correct | 401 ms | 46564 KB | Output is correct |
58 | Correct | 501 ms | 59744 KB | Output is correct |
59 | Correct | 2241 ms | 62588 KB | Output is correct |
60 | Correct | 1757 ms | 67240 KB | Output is correct |
61 | Correct | 1620 ms | 67960 KB | Output is correct |
62 | Correct | 1209 ms | 54580 KB | Output is correct |
63 | Correct | 308 ms | 34144 KB | Output is correct |
64 | Correct | 12 ms | 8004 KB | Output is correct |
65 | Correct | 11 ms | 8020 KB | Output is correct |
66 | Correct | 1208 ms | 54780 KB | Output is correct |
67 | Correct | 52 ms | 11544 KB | Output is correct |
68 | Correct | 88 ms | 14512 KB | Output is correct |
69 | Correct | 1900 ms | 62612 KB | Output is correct |
70 | Correct | 181 ms | 21704 KB | Output is correct |
71 | Correct | 620 ms | 50300 KB | Output is correct |
72 | Correct | 2028 ms | 62680 KB | Output is correct |
73 | Correct | 1253 ms | 54672 KB | Output is correct |