# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
603178 |
2022-07-23T16:35:41 Z |
FatihSolak |
Keys (IOI21_keys) |
C++17 |
|
623 ms |
112452 KB |
#include <bits/stdc++.h>
#define N 300005
using namespace std;
int group[N];
int find(int a){
if(a == group[a])return a;
return group[a] = find(group[a]);
}
bool merge(int a,int b){
a = find(a);
b = find(b);
if(a == b)
return 0;
group[a] = b;
return 1;
}
int low[N];
int tin[N];
bool is_bridge[2*N];
int vis[N];
bool vis2[N];
bool nowkeys[N];
vector<int> key[N];
vector<int> edges[N];
vector<pair<int,int>> adj[N];
vector<int> adj0[N];
int timer;
int tmp = -1;
void dfs(int v,int par){
tin[v] = timer++;
low[v] = tin[v];
vis[v] = tmp;
for(auto u:adj[v]){
if(u.first == par){
continue;
}
if(vis[u.second] != -1){
is_bridge[u.first] = 1;
if(vis[u.second] != vis[v]){
is_bridge[u.first] = 1;
}
else low[v] = min(low[v],tin[u.second]);
continue;
}
dfs(u.second,u.first);
if(low[u.second] > tin[v]){
is_bridge[u.first] = 1;
}
low[v] = min(low[v],low[u.second]);
}
}
void dfs2(int v){
vis2[v] = 1;
for(auto u:adj[v]){
if(is_bridge[u.first])continue;
merge(v,u.second);
if(vis2[u.second])continue;
dfs2(u.second);
}
}
int sz[N];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
int m = u.size();
vector<int> p(n,0);
for(int i = 0;i<m;i++){
adj0[u[i]].push_back(i);
adj0[v[i]].push_back(i);
}
for(int i = 0;i<n;i++){
group[i] = i;
}
for(int x = 0;x<4;x++){
for(int i = 0;i<n;i++){
key[i].clear();
edges[i].clear();
adj[i].clear();
vis[i] = -1;
vis2[i] = 0;
sz[i] = 0;
nowkeys[i] = 0;
}
for(int i = 0;i<2*m;i++){
is_bridge[i] = 0;
}
for(int i = 0;i<n;i++){
key[find(i)].push_back(r[i]);
for(auto x:adj0[i]){
edges[find(i)].push_back(x);
}
}
for(int i = 0;i<n;i++){
if(i != find(i))continue;
for(auto x:key[i]){
nowkeys[x] = 1;
}
for(auto x:edges[i]){
if(nowkeys[c[x]]){
if(find(u[x]) != i)
adj[i].push_back({x,find(u[x])});
if(find(v[x]) != i)
adj[i].push_back({x+m,find(v[x])});
}
}
for(auto x:key[i]){
nowkeys[x] = 0;
}
}
timer = 0;
for(int i = 0;i<n;i++){
if(vis[i] == -1 && i == find(i)){
tmp = i;
dfs(i,-1);
}
}
for(int i = 0;i<n;i++){
if(i == find(i) && !vis2[i]){
dfs2(i);
}
}
for(int i = 0;i<n;i++){
sz[find(i)]++;
}
int mini = 1e9;
for(int i = 0;i<n;i++){
if(sz[i] && adj[i].empty())
mini = min(mini,sz[i]);
}
for(int i = 0;i<n;i++){
if(sz[find(i)] == mini && adj[find(i)].empty()){
p[i] = 1;
}
else p[i] = 0;
}
}
return p;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28428 KB |
Output is correct |
2 |
Correct |
14 ms |
28500 KB |
Output is correct |
3 |
Correct |
14 ms |
28492 KB |
Output is correct |
4 |
Correct |
14 ms |
28548 KB |
Output is correct |
5 |
Correct |
13 ms |
28500 KB |
Output is correct |
6 |
Correct |
14 ms |
28512 KB |
Output is correct |
7 |
Correct |
14 ms |
28456 KB |
Output is correct |
8 |
Correct |
14 ms |
28500 KB |
Output is correct |
9 |
Correct |
14 ms |
28436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28428 KB |
Output is correct |
2 |
Correct |
14 ms |
28500 KB |
Output is correct |
3 |
Correct |
14 ms |
28492 KB |
Output is correct |
4 |
Correct |
14 ms |
28548 KB |
Output is correct |
5 |
Correct |
13 ms |
28500 KB |
Output is correct |
6 |
Correct |
14 ms |
28512 KB |
Output is correct |
7 |
Correct |
14 ms |
28456 KB |
Output is correct |
8 |
Correct |
14 ms |
28500 KB |
Output is correct |
9 |
Correct |
14 ms |
28436 KB |
Output is correct |
10 |
Correct |
15 ms |
28500 KB |
Output is correct |
11 |
Correct |
14 ms |
28500 KB |
Output is correct |
12 |
Correct |
14 ms |
28500 KB |
Output is correct |
13 |
Correct |
13 ms |
28500 KB |
Output is correct |
14 |
Correct |
13 ms |
28500 KB |
Output is correct |
15 |
Correct |
14 ms |
28476 KB |
Output is correct |
16 |
Correct |
14 ms |
28500 KB |
Output is correct |
17 |
Correct |
13 ms |
28500 KB |
Output is correct |
18 |
Correct |
15 ms |
28500 KB |
Output is correct |
19 |
Correct |
14 ms |
28500 KB |
Output is correct |
20 |
Correct |
13 ms |
28532 KB |
Output is correct |
21 |
Correct |
15 ms |
28504 KB |
Output is correct |
22 |
Correct |
14 ms |
28500 KB |
Output is correct |
23 |
Correct |
14 ms |
28500 KB |
Output is correct |
24 |
Correct |
17 ms |
28504 KB |
Output is correct |
25 |
Correct |
19 ms |
28528 KB |
Output is correct |
26 |
Correct |
15 ms |
28500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28428 KB |
Output is correct |
2 |
Correct |
14 ms |
28500 KB |
Output is correct |
3 |
Correct |
14 ms |
28492 KB |
Output is correct |
4 |
Correct |
14 ms |
28548 KB |
Output is correct |
5 |
Correct |
13 ms |
28500 KB |
Output is correct |
6 |
Correct |
14 ms |
28512 KB |
Output is correct |
7 |
Correct |
14 ms |
28456 KB |
Output is correct |
8 |
Correct |
14 ms |
28500 KB |
Output is correct |
9 |
Correct |
14 ms |
28436 KB |
Output is correct |
10 |
Correct |
15 ms |
28500 KB |
Output is correct |
11 |
Correct |
14 ms |
28500 KB |
Output is correct |
12 |
Correct |
14 ms |
28500 KB |
Output is correct |
13 |
Correct |
13 ms |
28500 KB |
Output is correct |
14 |
Correct |
13 ms |
28500 KB |
Output is correct |
15 |
Correct |
14 ms |
28476 KB |
Output is correct |
16 |
Correct |
14 ms |
28500 KB |
Output is correct |
17 |
Correct |
13 ms |
28500 KB |
Output is correct |
18 |
Correct |
15 ms |
28500 KB |
Output is correct |
19 |
Correct |
14 ms |
28500 KB |
Output is correct |
20 |
Correct |
13 ms |
28532 KB |
Output is correct |
21 |
Correct |
15 ms |
28504 KB |
Output is correct |
22 |
Correct |
14 ms |
28500 KB |
Output is correct |
23 |
Correct |
14 ms |
28500 KB |
Output is correct |
24 |
Correct |
17 ms |
28504 KB |
Output is correct |
25 |
Correct |
19 ms |
28528 KB |
Output is correct |
26 |
Correct |
15 ms |
28500 KB |
Output is correct |
27 |
Correct |
15 ms |
28848 KB |
Output is correct |
28 |
Correct |
16 ms |
28856 KB |
Output is correct |
29 |
Correct |
15 ms |
28828 KB |
Output is correct |
30 |
Correct |
14 ms |
28716 KB |
Output is correct |
31 |
Correct |
15 ms |
28584 KB |
Output is correct |
32 |
Correct |
15 ms |
28580 KB |
Output is correct |
33 |
Correct |
14 ms |
28628 KB |
Output is correct |
34 |
Correct |
14 ms |
28756 KB |
Output is correct |
35 |
Correct |
14 ms |
28628 KB |
Output is correct |
36 |
Correct |
15 ms |
28896 KB |
Output is correct |
37 |
Correct |
15 ms |
28960 KB |
Output is correct |
38 |
Correct |
16 ms |
28944 KB |
Output is correct |
39 |
Correct |
16 ms |
29012 KB |
Output is correct |
40 |
Correct |
15 ms |
28624 KB |
Output is correct |
41 |
Correct |
16 ms |
28756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28428 KB |
Output is correct |
2 |
Correct |
14 ms |
28500 KB |
Output is correct |
3 |
Correct |
14 ms |
28492 KB |
Output is correct |
4 |
Correct |
14 ms |
28548 KB |
Output is correct |
5 |
Correct |
13 ms |
28500 KB |
Output is correct |
6 |
Correct |
14 ms |
28512 KB |
Output is correct |
7 |
Correct |
14 ms |
28456 KB |
Output is correct |
8 |
Correct |
14 ms |
28500 KB |
Output is correct |
9 |
Correct |
14 ms |
28436 KB |
Output is correct |
10 |
Correct |
326 ms |
57996 KB |
Output is correct |
11 |
Correct |
489 ms |
93388 KB |
Output is correct |
12 |
Correct |
112 ms |
38812 KB |
Output is correct |
13 |
Correct |
623 ms |
82392 KB |
Output is correct |
14 |
Correct |
278 ms |
112452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28428 KB |
Output is correct |
2 |
Correct |
14 ms |
28500 KB |
Output is correct |
3 |
Correct |
14 ms |
28492 KB |
Output is correct |
4 |
Correct |
14 ms |
28548 KB |
Output is correct |
5 |
Correct |
13 ms |
28500 KB |
Output is correct |
6 |
Correct |
14 ms |
28512 KB |
Output is correct |
7 |
Correct |
14 ms |
28456 KB |
Output is correct |
8 |
Correct |
14 ms |
28500 KB |
Output is correct |
9 |
Correct |
14 ms |
28436 KB |
Output is correct |
10 |
Correct |
15 ms |
28500 KB |
Output is correct |
11 |
Correct |
14 ms |
28500 KB |
Output is correct |
12 |
Correct |
14 ms |
28500 KB |
Output is correct |
13 |
Correct |
13 ms |
28500 KB |
Output is correct |
14 |
Correct |
13 ms |
28500 KB |
Output is correct |
15 |
Correct |
14 ms |
28476 KB |
Output is correct |
16 |
Correct |
14 ms |
28500 KB |
Output is correct |
17 |
Correct |
13 ms |
28500 KB |
Output is correct |
18 |
Correct |
15 ms |
28500 KB |
Output is correct |
19 |
Correct |
14 ms |
28500 KB |
Output is correct |
20 |
Correct |
13 ms |
28532 KB |
Output is correct |
21 |
Correct |
15 ms |
28504 KB |
Output is correct |
22 |
Correct |
14 ms |
28500 KB |
Output is correct |
23 |
Correct |
14 ms |
28500 KB |
Output is correct |
24 |
Correct |
17 ms |
28504 KB |
Output is correct |
25 |
Correct |
19 ms |
28528 KB |
Output is correct |
26 |
Correct |
15 ms |
28500 KB |
Output is correct |
27 |
Correct |
15 ms |
28848 KB |
Output is correct |
28 |
Correct |
16 ms |
28856 KB |
Output is correct |
29 |
Correct |
15 ms |
28828 KB |
Output is correct |
30 |
Correct |
14 ms |
28716 KB |
Output is correct |
31 |
Correct |
15 ms |
28584 KB |
Output is correct |
32 |
Correct |
15 ms |
28580 KB |
Output is correct |
33 |
Correct |
14 ms |
28628 KB |
Output is correct |
34 |
Correct |
14 ms |
28756 KB |
Output is correct |
35 |
Correct |
14 ms |
28628 KB |
Output is correct |
36 |
Correct |
15 ms |
28896 KB |
Output is correct |
37 |
Correct |
15 ms |
28960 KB |
Output is correct |
38 |
Correct |
16 ms |
28944 KB |
Output is correct |
39 |
Correct |
16 ms |
29012 KB |
Output is correct |
40 |
Correct |
15 ms |
28624 KB |
Output is correct |
41 |
Correct |
16 ms |
28756 KB |
Output is correct |
42 |
Correct |
326 ms |
57996 KB |
Output is correct |
43 |
Correct |
489 ms |
93388 KB |
Output is correct |
44 |
Correct |
112 ms |
38812 KB |
Output is correct |
45 |
Correct |
623 ms |
82392 KB |
Output is correct |
46 |
Correct |
278 ms |
112452 KB |
Output is correct |
47 |
Correct |
16 ms |
28448 KB |
Output is correct |
48 |
Correct |
14 ms |
28516 KB |
Output is correct |
49 |
Correct |
16 ms |
28500 KB |
Output is correct |
50 |
Correct |
260 ms |
102976 KB |
Output is correct |
51 |
Correct |
292 ms |
102592 KB |
Output is correct |
52 |
Correct |
306 ms |
62180 KB |
Output is correct |
53 |
Correct |
308 ms |
62084 KB |
Output is correct |
54 |
Correct |
310 ms |
62180 KB |
Output is correct |
55 |
Correct |
284 ms |
58512 KB |
Output is correct |
56 |
Correct |
529 ms |
86048 KB |
Output is correct |
57 |
Correct |
348 ms |
79104 KB |
Output is correct |
58 |
Correct |
391 ms |
85912 KB |
Output is correct |
59 |
Correct |
468 ms |
80564 KB |
Output is correct |
60 |
Correct |
488 ms |
89740 KB |
Output is correct |
61 |
Correct |
479 ms |
89756 KB |
Output is correct |
62 |
Correct |
424 ms |
68280 KB |
Output is correct |
63 |
Correct |
236 ms |
72472 KB |
Output is correct |
64 |
Correct |
21 ms |
29908 KB |
Output is correct |
65 |
Correct |
19 ms |
29908 KB |
Output is correct |
66 |
Correct |
419 ms |
68300 KB |
Output is correct |
67 |
Correct |
48 ms |
36876 KB |
Output is correct |
68 |
Correct |
61 ms |
42484 KB |
Output is correct |
69 |
Correct |
486 ms |
78504 KB |
Output is correct |
70 |
Correct |
103 ms |
56256 KB |
Output is correct |
71 |
Correct |
280 ms |
112304 KB |
Output is correct |
72 |
Correct |
518 ms |
80604 KB |
Output is correct |
73 |
Correct |
439 ms |
68300 KB |
Output is correct |