# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
837282 |
2023-08-25T09:07:10 Z |
QwertyPi |
Keys (IOI21_keys) |
C++17 |
|
1615 ms |
146824 KB |
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 3e5 + 11;
struct edge{
int to, c;
bool operator< (const edge& o) const {
return c < o.c || (c == o.c && to < o.to);
}
};
set<int> _vertexes[N_MAX];
set<int> _keys[N_MAX];
set<edge> _edges[N_MAX];
set<edge> _ok_edges[N_MAX];
struct node{
set<int>* vertexes;
set<int>* keys;
set<edge>* edges;
set<edge>* ok_edges;
int find_next();
void clear();
} nodes[N_MAX];
int prv[N_MAX], _size[N_MAX];
bool vis[N_MAX], done[N_MAX];
void fill_none(int v){
int x = v;
while(!done[x]){
for(auto y : *nodes[x].vertexes){
done[y] = true; _size[y] = 1 << 30;
}
nodes[x].clear();
x = prv[x];
}
}
int back_number = -1;
void node::clear(){
vertexes->clear();
keys->clear();
edges->clear();
}
int node::find_next(){
while(ok_edges->size()){
int u = ok_edges->begin()->to;
ok_edges->erase(ok_edges->begin());
if(!vertexes->count(u)) return u;
}
return -1;
}
void merge(int u, int v){
// OK Edges
if(nodes[u].ok_edges->size() < nodes[v].ok_edges->size()){
swap(nodes[u].ok_edges, nodes[v].ok_edges);
}
for(auto e : *nodes[v].ok_edges){
nodes[u].ok_edges->insert(e);
}
// Edges
if(nodes[u].edges->size() + nodes[u].keys->size() < nodes[v].keys->size() + nodes[v].keys->size()){
swap(nodes[u].edges, nodes[v].edges);
swap(nodes[u].keys, nodes[v].keys);
}
for(auto x : *nodes[v].keys){
auto ptr = nodes[u].edges->lower_bound({-1, x});
while(ptr != nodes[u].edges->end() && ptr->c == x){
nodes[u].ok_edges->insert({ptr->to, ptr->c});
nodes[u].edges->erase(ptr);
ptr = nodes[u].edges->lower_bound({-1, x});
}
}
for(auto [to, x] : *nodes[v].edges){
if(nodes[u].keys->count(x)){
nodes[u].ok_edges->insert({to, x});
}else{
nodes[u].edges->insert({to, x});
}
}
// Vertexes
if(nodes[u].vertexes->size() < nodes[v].vertexes->size()){
swap(nodes[u].vertexes, nodes[v].vertexes);
}
for(auto x : *nodes[v].vertexes){
nodes[u].vertexes->insert(x);
}
// Keys
if(nodes[u].keys->size() < nodes[v].keys->size()){
swap(nodes[u].keys, nodes[v].keys);
}
for(auto x : *nodes[v].keys){
nodes[u].keys->insert(x);
}
nodes[v].clear();
}
void dfs(int v, int pa = -1){
vis[v] = true;
while(true){
int u = nodes[v].find_next();
if(u == -1) break;
if(done[u]) {
fill_none(v);
return;
} else if(vis[u]) {
back_number = u;
merge(prv[v], v);
return;
} else {
prv[u] = v; dfs(u, v);
if(back_number != -1){
if(nodes[v].vertexes->count(back_number)){
back_number = -1;
}else{
merge(prv[v], v);
return;
}
}
if(done[v]) return;
}
}
for(auto u : *nodes[v].vertexes){
done[u] = true; _size[u] = nodes[v].vertexes->size();
}
fill_none(prv[v]);
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size(), m = u.size();
vector<int> ans(n);
for(int i = 0; i < n; i++){
nodes[i].vertexes = &_vertexes[i];
nodes[i].keys = &_keys[i];
nodes[i].edges = &_edges[i];
nodes[i].ok_edges = &_ok_edges[i];
}
for(int i = 0; i < n; i++) nodes[i].vertexes->insert(i);
for(int i = 0; i < n; i++) nodes[i].keys->insert(r[i]);
for(int i = 0; i < m; i++) {
if(r[u[i]] == c[i]) nodes[u[i]].ok_edges->insert({v[i], c[i]});
else nodes[u[i]].edges->insert({v[i], c[i]});
if(r[v[i]] == c[i]) nodes[v[i]].ok_edges->insert({u[i], c[i]});
else nodes[v[i]].edges->insert({u[i], c[i]});
}
for(int i = 0; i < n; i++){
if(!vis[i]){
dfs(i);
}
}
for(int i = 0; i < n; i++) assert(done[i]);
int min_size = *min_element(_size, _size + n);
for(int i = 0; i < n; i++){
ans[i] = _size[i] == min_size;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
56660 KB |
Output is correct |
2 |
Correct |
28 ms |
56644 KB |
Output is correct |
3 |
Correct |
27 ms |
56596 KB |
Output is correct |
4 |
Correct |
26 ms |
56724 KB |
Output is correct |
5 |
Correct |
28 ms |
56660 KB |
Output is correct |
6 |
Correct |
27 ms |
56660 KB |
Output is correct |
7 |
Correct |
28 ms |
56660 KB |
Output is correct |
8 |
Correct |
27 ms |
56660 KB |
Output is correct |
9 |
Correct |
33 ms |
56652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
56660 KB |
Output is correct |
2 |
Correct |
28 ms |
56644 KB |
Output is correct |
3 |
Correct |
27 ms |
56596 KB |
Output is correct |
4 |
Correct |
26 ms |
56724 KB |
Output is correct |
5 |
Correct |
28 ms |
56660 KB |
Output is correct |
6 |
Correct |
27 ms |
56660 KB |
Output is correct |
7 |
Correct |
28 ms |
56660 KB |
Output is correct |
8 |
Correct |
27 ms |
56660 KB |
Output is correct |
9 |
Correct |
33 ms |
56652 KB |
Output is correct |
10 |
Correct |
27 ms |
56660 KB |
Output is correct |
11 |
Correct |
32 ms |
56660 KB |
Output is correct |
12 |
Correct |
27 ms |
56692 KB |
Output is correct |
13 |
Correct |
27 ms |
56676 KB |
Output is correct |
14 |
Correct |
28 ms |
56652 KB |
Output is correct |
15 |
Correct |
28 ms |
56660 KB |
Output is correct |
16 |
Correct |
30 ms |
56868 KB |
Output is correct |
17 |
Correct |
28 ms |
56660 KB |
Output is correct |
18 |
Correct |
28 ms |
56704 KB |
Output is correct |
19 |
Correct |
30 ms |
56660 KB |
Output is correct |
20 |
Correct |
28 ms |
56656 KB |
Output is correct |
21 |
Correct |
28 ms |
56760 KB |
Output is correct |
22 |
Correct |
28 ms |
56660 KB |
Output is correct |
23 |
Correct |
28 ms |
56696 KB |
Output is correct |
24 |
Correct |
27 ms |
56644 KB |
Output is correct |
25 |
Correct |
28 ms |
56648 KB |
Output is correct |
26 |
Correct |
30 ms |
56660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
56660 KB |
Output is correct |
2 |
Correct |
28 ms |
56644 KB |
Output is correct |
3 |
Correct |
27 ms |
56596 KB |
Output is correct |
4 |
Correct |
26 ms |
56724 KB |
Output is correct |
5 |
Correct |
28 ms |
56660 KB |
Output is correct |
6 |
Correct |
27 ms |
56660 KB |
Output is correct |
7 |
Correct |
28 ms |
56660 KB |
Output is correct |
8 |
Correct |
27 ms |
56660 KB |
Output is correct |
9 |
Correct |
33 ms |
56652 KB |
Output is correct |
10 |
Correct |
27 ms |
56660 KB |
Output is correct |
11 |
Correct |
32 ms |
56660 KB |
Output is correct |
12 |
Correct |
27 ms |
56692 KB |
Output is correct |
13 |
Correct |
27 ms |
56676 KB |
Output is correct |
14 |
Correct |
28 ms |
56652 KB |
Output is correct |
15 |
Correct |
28 ms |
56660 KB |
Output is correct |
16 |
Correct |
30 ms |
56868 KB |
Output is correct |
17 |
Correct |
28 ms |
56660 KB |
Output is correct |
18 |
Correct |
28 ms |
56704 KB |
Output is correct |
19 |
Correct |
30 ms |
56660 KB |
Output is correct |
20 |
Correct |
28 ms |
56656 KB |
Output is correct |
21 |
Correct |
28 ms |
56760 KB |
Output is correct |
22 |
Correct |
28 ms |
56660 KB |
Output is correct |
23 |
Correct |
28 ms |
56696 KB |
Output is correct |
24 |
Correct |
27 ms |
56644 KB |
Output is correct |
25 |
Correct |
28 ms |
56648 KB |
Output is correct |
26 |
Correct |
30 ms |
56660 KB |
Output is correct |
27 |
Correct |
29 ms |
57172 KB |
Output is correct |
28 |
Correct |
28 ms |
57172 KB |
Output is correct |
29 |
Correct |
28 ms |
57172 KB |
Output is correct |
30 |
Correct |
28 ms |
56916 KB |
Output is correct |
31 |
Correct |
28 ms |
56908 KB |
Output is correct |
32 |
Correct |
28 ms |
56788 KB |
Output is correct |
33 |
Correct |
28 ms |
56916 KB |
Output is correct |
34 |
Correct |
28 ms |
56916 KB |
Output is correct |
35 |
Correct |
29 ms |
56908 KB |
Output is correct |
36 |
Correct |
33 ms |
57172 KB |
Output is correct |
37 |
Correct |
34 ms |
57164 KB |
Output is correct |
38 |
Correct |
30 ms |
57300 KB |
Output is correct |
39 |
Correct |
31 ms |
57300 KB |
Output is correct |
40 |
Correct |
28 ms |
56916 KB |
Output is correct |
41 |
Correct |
34 ms |
57044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
56660 KB |
Output is correct |
2 |
Correct |
28 ms |
56644 KB |
Output is correct |
3 |
Correct |
27 ms |
56596 KB |
Output is correct |
4 |
Correct |
26 ms |
56724 KB |
Output is correct |
5 |
Correct |
28 ms |
56660 KB |
Output is correct |
6 |
Correct |
27 ms |
56660 KB |
Output is correct |
7 |
Correct |
28 ms |
56660 KB |
Output is correct |
8 |
Correct |
27 ms |
56660 KB |
Output is correct |
9 |
Correct |
33 ms |
56652 KB |
Output is correct |
10 |
Correct |
669 ms |
113240 KB |
Output is correct |
11 |
Correct |
762 ms |
139916 KB |
Output is correct |
12 |
Correct |
100 ms |
72044 KB |
Output is correct |
13 |
Correct |
471 ms |
134212 KB |
Output is correct |
14 |
Correct |
283 ms |
141348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
56660 KB |
Output is correct |
2 |
Correct |
28 ms |
56644 KB |
Output is correct |
3 |
Correct |
27 ms |
56596 KB |
Output is correct |
4 |
Correct |
26 ms |
56724 KB |
Output is correct |
5 |
Correct |
28 ms |
56660 KB |
Output is correct |
6 |
Correct |
27 ms |
56660 KB |
Output is correct |
7 |
Correct |
28 ms |
56660 KB |
Output is correct |
8 |
Correct |
27 ms |
56660 KB |
Output is correct |
9 |
Correct |
33 ms |
56652 KB |
Output is correct |
10 |
Correct |
27 ms |
56660 KB |
Output is correct |
11 |
Correct |
32 ms |
56660 KB |
Output is correct |
12 |
Correct |
27 ms |
56692 KB |
Output is correct |
13 |
Correct |
27 ms |
56676 KB |
Output is correct |
14 |
Correct |
28 ms |
56652 KB |
Output is correct |
15 |
Correct |
28 ms |
56660 KB |
Output is correct |
16 |
Correct |
30 ms |
56868 KB |
Output is correct |
17 |
Correct |
28 ms |
56660 KB |
Output is correct |
18 |
Correct |
28 ms |
56704 KB |
Output is correct |
19 |
Correct |
30 ms |
56660 KB |
Output is correct |
20 |
Correct |
28 ms |
56656 KB |
Output is correct |
21 |
Correct |
28 ms |
56760 KB |
Output is correct |
22 |
Correct |
28 ms |
56660 KB |
Output is correct |
23 |
Correct |
28 ms |
56696 KB |
Output is correct |
24 |
Correct |
27 ms |
56644 KB |
Output is correct |
25 |
Correct |
28 ms |
56648 KB |
Output is correct |
26 |
Correct |
30 ms |
56660 KB |
Output is correct |
27 |
Correct |
29 ms |
57172 KB |
Output is correct |
28 |
Correct |
28 ms |
57172 KB |
Output is correct |
29 |
Correct |
28 ms |
57172 KB |
Output is correct |
30 |
Correct |
28 ms |
56916 KB |
Output is correct |
31 |
Correct |
28 ms |
56908 KB |
Output is correct |
32 |
Correct |
28 ms |
56788 KB |
Output is correct |
33 |
Correct |
28 ms |
56916 KB |
Output is correct |
34 |
Correct |
28 ms |
56916 KB |
Output is correct |
35 |
Correct |
29 ms |
56908 KB |
Output is correct |
36 |
Correct |
33 ms |
57172 KB |
Output is correct |
37 |
Correct |
34 ms |
57164 KB |
Output is correct |
38 |
Correct |
30 ms |
57300 KB |
Output is correct |
39 |
Correct |
31 ms |
57300 KB |
Output is correct |
40 |
Correct |
28 ms |
56916 KB |
Output is correct |
41 |
Correct |
34 ms |
57044 KB |
Output is correct |
42 |
Correct |
669 ms |
113240 KB |
Output is correct |
43 |
Correct |
762 ms |
139916 KB |
Output is correct |
44 |
Correct |
100 ms |
72044 KB |
Output is correct |
45 |
Correct |
471 ms |
134212 KB |
Output is correct |
46 |
Correct |
283 ms |
141348 KB |
Output is correct |
47 |
Correct |
27 ms |
56660 KB |
Output is correct |
48 |
Correct |
28 ms |
56660 KB |
Output is correct |
49 |
Correct |
29 ms |
56660 KB |
Output is correct |
50 |
Correct |
299 ms |
140236 KB |
Output is correct |
51 |
Correct |
335 ms |
143408 KB |
Output is correct |
52 |
Correct |
320 ms |
114508 KB |
Output is correct |
53 |
Correct |
334 ms |
114508 KB |
Output is correct |
54 |
Correct |
339 ms |
114764 KB |
Output is correct |
55 |
Correct |
771 ms |
115832 KB |
Output is correct |
56 |
Correct |
589 ms |
146824 KB |
Output is correct |
57 |
Correct |
448 ms |
142668 KB |
Output is correct |
58 |
Correct |
535 ms |
142552 KB |
Output is correct |
59 |
Correct |
1494 ms |
133420 KB |
Output is correct |
60 |
Correct |
1615 ms |
140392 KB |
Output is correct |
61 |
Correct |
1584 ms |
140692 KB |
Output is correct |
62 |
Correct |
1243 ms |
117268 KB |
Output is correct |
63 |
Correct |
242 ms |
123276 KB |
Output is correct |
64 |
Correct |
32 ms |
58092 KB |
Output is correct |
65 |
Correct |
31 ms |
58068 KB |
Output is correct |
66 |
Correct |
1262 ms |
117404 KB |
Output is correct |
67 |
Correct |
49 ms |
65228 KB |
Output is correct |
68 |
Correct |
64 ms |
70760 KB |
Output is correct |
69 |
Correct |
1430 ms |
132784 KB |
Output is correct |
70 |
Correct |
100 ms |
84924 KB |
Output is correct |
71 |
Correct |
266 ms |
141856 KB |
Output is correct |
72 |
Correct |
1535 ms |
134380 KB |
Output is correct |
73 |
Correct |
1282 ms |
117344 KB |
Output is correct |