# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
979413 |
2024-05-10T21:57:31 Z |
alontanay |
Keys (IOI21_keys) |
C++17 |
|
609 ms |
298880 KB |
#include "keys.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define NEW_STATE 0
#define ACTIVE_STATE 1
#define OLD_STATE 2
#define NO_POS -1
using namespace std;
using pi = pair<int,int>;
const int MAX_N = 3e5+5;
namespace dsu {
int sz[MAX_N], root[MAX_N], L[MAX_N];
int PTR_pos[MAX_N];
stack<int> pos[MAX_N];
int PTR_ord_future[MAX_N];
priority_queue<pi> ord_future[MAX_N];
void init(int n) {
for(int i = 0; i < n; i ++) {
sz[i] = 1;
root[i] = i;
PTR_pos[i] = i;
PTR_ord_future[i] = i;
}
}
int get_root(int node) {
if(root[node] == node) {return node;}
return root[node] = get_root(root[node]);
}
void add_pos(int node, int ne) {
pos[PTR_pos[get_root(node)]].push(ne);
}
int poll_pos(int node) {
int ptr = PTR_pos[get_root(node)];
if(pos[ptr].empty()) { return NO_POS; }
int top = pos[ptr].top();
pos[ptr].pop();
return top;
}
bool are_joined(int a, int b) {
return get_root(a) == get_root(b);
}
int merge(int a, int b) {
a = get_root(a);
b = get_root(b);
if(a == b) { return a; }
if(sz[a] < sz[b]) {
swap(a,b);
}
L[a] = min(L[a],L[b]);
root[b] = a;
{
int big_ptr = PTR_pos[a];
int small_ptr = PTR_pos[b];
if(pos[big_ptr].size() < pos[small_ptr].size()) {
swap(big_ptr,small_ptr);
}
PTR_pos[a] = big_ptr;
stack<int> &big_pos = pos[big_ptr];
stack<int> &small_pos = pos[small_ptr];
while(!small_pos.empty()) {
big_pos.push(small_pos.top());
small_pos.pop();
}
}
{
int big_ptr = PTR_ord_future[a];
int small_ptr = PTR_ord_future[b];
if(ord_future[big_ptr].size() < ord_future[small_ptr].size()) {
swap(big_ptr,small_ptr);
}
PTR_ord_future[a] = big_ptr;
priority_queue<pi> &big_ord_future = ord_future[big_ptr];
priority_queue<pi> &small_ord_future = ord_future[small_ptr];
while(!small_ord_future.empty()) {
big_ord_future.push(small_ord_future.top());
small_ord_future.pop();
}
while(!big_ord_future.empty() && big_ord_future.top().f >= L[a]) {
pos[PTR_pos[a]].push(big_ord_future.top().s);
big_ord_future.pop();
}
}
return a;
}
}
vector<pi> nei[MAX_N];
vector<pi> need_key[MAX_N];
int state[MAX_N];
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(), m = u.size();
dsu::init(n);
for(int i = 0;i < m; i ++) {
int a = u[i], b = v[i], t = c[i];
nei[a].push_back({b,t});
nei[b].push_back({a,t});
}
vector<int> last_occ(n);
int cidx = 0;
vector<int> res;
int opt_score = n;
vector<int> once(n);
for(int i = 0; i < n; i ++) {
if(state[i] != NEW_STATE) { continue; }
stack<int> UPD_need_key;
stack<int> reached_nodes;
bool reached_old = false;
int node = i;
stack<int> comp_stack;
while(true) {
cidx++;
reached_nodes.push(node);
int key = r[node];
dsu::L[node] = cidx;
comp_stack.push(node);
last_occ[key] = cidx;
state[node] = ACTIVE_STATE;
for(auto &[ne, req] : nei[node]) {
UPD_need_key.push(req);
need_key[req].push_back({node,ne});
dsu::ord_future[node].push({last_occ[req],ne});
}
for(pi edge : need_key[key]) {
dsu::add_pos(edge.f,edge.s);
}
need_key[key].clear();
int next_node;
bool converged = false;
while(true) {
next_node = dsu::poll_pos(node);
if(next_node == NO_POS) {
converged = true;
break;
}
if(state[next_node] == OLD_STATE) {
reached_old = true;
break;
}
if(state[next_node] == NEW_STATE) {
break;
}
while(comp_stack.size() >= 2 && !dsu::are_joined(node,next_node)) {
int top = comp_stack.top();
comp_stack.pop();
int bef = comp_stack.top();
comp_stack.pop();
int new_root = dsu::merge(top,bef);
comp_stack.push(new_root);
}
}
if(reached_old || converged) {
break;
}
node = next_node;
}
vector<int> base_comp;
base_comp.reserve(reached_nodes.size());
while(!reached_nodes.empty()) {
int top = reached_nodes.top();
if(!reached_old && dsu::are_joined(node, top)) {
base_comp.push_back(top);
}
reached_nodes.pop();
state[top] = OLD_STATE;
}
if(!reached_old) {
int score = base_comp.size();
if(score < opt_score) {
opt_score = score;
res.clear();
}
if(score == opt_score) {
res.insert(res.end(),base_comp.begin(),base_comp.end());
}
}
while(!UPD_need_key.empty()) {
int key = UPD_need_key.top();
UPD_need_key.pop();
need_key[key].clear();
}
}
vector<int> ans(n);
for(int r : res) {
ans[r] = 1;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
232020 KB |
Output is correct |
2 |
Correct |
99 ms |
232024 KB |
Output is correct |
3 |
Correct |
96 ms |
232016 KB |
Output is correct |
4 |
Correct |
99 ms |
232264 KB |
Output is correct |
5 |
Correct |
110 ms |
232156 KB |
Output is correct |
6 |
Correct |
104 ms |
232452 KB |
Output is correct |
7 |
Correct |
96 ms |
232016 KB |
Output is correct |
8 |
Correct |
98 ms |
232092 KB |
Output is correct |
9 |
Correct |
99 ms |
232096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
232020 KB |
Output is correct |
2 |
Correct |
99 ms |
232024 KB |
Output is correct |
3 |
Correct |
96 ms |
232016 KB |
Output is correct |
4 |
Correct |
99 ms |
232264 KB |
Output is correct |
5 |
Correct |
110 ms |
232156 KB |
Output is correct |
6 |
Correct |
104 ms |
232452 KB |
Output is correct |
7 |
Correct |
96 ms |
232016 KB |
Output is correct |
8 |
Correct |
98 ms |
232092 KB |
Output is correct |
9 |
Correct |
99 ms |
232096 KB |
Output is correct |
10 |
Correct |
110 ms |
232276 KB |
Output is correct |
11 |
Correct |
99 ms |
232160 KB |
Output is correct |
12 |
Correct |
101 ms |
232276 KB |
Output is correct |
13 |
Correct |
100 ms |
232016 KB |
Output is correct |
14 |
Correct |
99 ms |
232024 KB |
Output is correct |
15 |
Correct |
97 ms |
232020 KB |
Output is correct |
16 |
Correct |
97 ms |
232016 KB |
Output is correct |
17 |
Correct |
99 ms |
232016 KB |
Output is correct |
18 |
Correct |
103 ms |
232424 KB |
Output is correct |
19 |
Correct |
101 ms |
232168 KB |
Output is correct |
20 |
Correct |
100 ms |
232020 KB |
Output is correct |
21 |
Correct |
102 ms |
232532 KB |
Output is correct |
22 |
Correct |
103 ms |
232056 KB |
Output is correct |
23 |
Correct |
107 ms |
232028 KB |
Output is correct |
24 |
Correct |
99 ms |
232272 KB |
Output is correct |
25 |
Correct |
102 ms |
232028 KB |
Output is correct |
26 |
Correct |
97 ms |
232016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
232020 KB |
Output is correct |
2 |
Correct |
99 ms |
232024 KB |
Output is correct |
3 |
Correct |
96 ms |
232016 KB |
Output is correct |
4 |
Correct |
99 ms |
232264 KB |
Output is correct |
5 |
Correct |
110 ms |
232156 KB |
Output is correct |
6 |
Correct |
104 ms |
232452 KB |
Output is correct |
7 |
Correct |
96 ms |
232016 KB |
Output is correct |
8 |
Correct |
98 ms |
232092 KB |
Output is correct |
9 |
Correct |
99 ms |
232096 KB |
Output is correct |
10 |
Correct |
110 ms |
232276 KB |
Output is correct |
11 |
Correct |
99 ms |
232160 KB |
Output is correct |
12 |
Correct |
101 ms |
232276 KB |
Output is correct |
13 |
Correct |
100 ms |
232016 KB |
Output is correct |
14 |
Correct |
99 ms |
232024 KB |
Output is correct |
15 |
Correct |
97 ms |
232020 KB |
Output is correct |
16 |
Correct |
97 ms |
232016 KB |
Output is correct |
17 |
Correct |
99 ms |
232016 KB |
Output is correct |
18 |
Correct |
103 ms |
232424 KB |
Output is correct |
19 |
Correct |
101 ms |
232168 KB |
Output is correct |
20 |
Correct |
100 ms |
232020 KB |
Output is correct |
21 |
Correct |
102 ms |
232532 KB |
Output is correct |
22 |
Correct |
103 ms |
232056 KB |
Output is correct |
23 |
Correct |
107 ms |
232028 KB |
Output is correct |
24 |
Correct |
99 ms |
232272 KB |
Output is correct |
25 |
Correct |
102 ms |
232028 KB |
Output is correct |
26 |
Correct |
97 ms |
232016 KB |
Output is correct |
27 |
Correct |
120 ms |
232528 KB |
Output is correct |
28 |
Correct |
100 ms |
232560 KB |
Output is correct |
29 |
Correct |
102 ms |
232528 KB |
Output is correct |
30 |
Correct |
113 ms |
232532 KB |
Output is correct |
31 |
Correct |
101 ms |
232320 KB |
Output is correct |
32 |
Correct |
99 ms |
232276 KB |
Output is correct |
33 |
Correct |
116 ms |
232360 KB |
Output is correct |
34 |
Correct |
112 ms |
232300 KB |
Output is correct |
35 |
Correct |
98 ms |
232220 KB |
Output is correct |
36 |
Correct |
114 ms |
232396 KB |
Output is correct |
37 |
Correct |
99 ms |
232532 KB |
Output is correct |
38 |
Correct |
103 ms |
232564 KB |
Output is correct |
39 |
Correct |
102 ms |
232540 KB |
Output is correct |
40 |
Correct |
101 ms |
232272 KB |
Output is correct |
41 |
Correct |
102 ms |
232252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
232020 KB |
Output is correct |
2 |
Correct |
99 ms |
232024 KB |
Output is correct |
3 |
Correct |
96 ms |
232016 KB |
Output is correct |
4 |
Correct |
99 ms |
232264 KB |
Output is correct |
5 |
Correct |
110 ms |
232156 KB |
Output is correct |
6 |
Correct |
104 ms |
232452 KB |
Output is correct |
7 |
Correct |
96 ms |
232016 KB |
Output is correct |
8 |
Correct |
98 ms |
232092 KB |
Output is correct |
9 |
Correct |
99 ms |
232096 KB |
Output is correct |
10 |
Correct |
344 ms |
260940 KB |
Output is correct |
11 |
Correct |
444 ms |
275680 KB |
Output is correct |
12 |
Correct |
145 ms |
239124 KB |
Output is correct |
13 |
Correct |
394 ms |
265892 KB |
Output is correct |
14 |
Correct |
318 ms |
272372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
232020 KB |
Output is correct |
2 |
Correct |
99 ms |
232024 KB |
Output is correct |
3 |
Correct |
96 ms |
232016 KB |
Output is correct |
4 |
Correct |
99 ms |
232264 KB |
Output is correct |
5 |
Correct |
110 ms |
232156 KB |
Output is correct |
6 |
Correct |
104 ms |
232452 KB |
Output is correct |
7 |
Correct |
96 ms |
232016 KB |
Output is correct |
8 |
Correct |
98 ms |
232092 KB |
Output is correct |
9 |
Correct |
99 ms |
232096 KB |
Output is correct |
10 |
Correct |
110 ms |
232276 KB |
Output is correct |
11 |
Correct |
99 ms |
232160 KB |
Output is correct |
12 |
Correct |
101 ms |
232276 KB |
Output is correct |
13 |
Correct |
100 ms |
232016 KB |
Output is correct |
14 |
Correct |
99 ms |
232024 KB |
Output is correct |
15 |
Correct |
97 ms |
232020 KB |
Output is correct |
16 |
Correct |
97 ms |
232016 KB |
Output is correct |
17 |
Correct |
99 ms |
232016 KB |
Output is correct |
18 |
Correct |
103 ms |
232424 KB |
Output is correct |
19 |
Correct |
101 ms |
232168 KB |
Output is correct |
20 |
Correct |
100 ms |
232020 KB |
Output is correct |
21 |
Correct |
102 ms |
232532 KB |
Output is correct |
22 |
Correct |
103 ms |
232056 KB |
Output is correct |
23 |
Correct |
107 ms |
232028 KB |
Output is correct |
24 |
Correct |
99 ms |
232272 KB |
Output is correct |
25 |
Correct |
102 ms |
232028 KB |
Output is correct |
26 |
Correct |
97 ms |
232016 KB |
Output is correct |
27 |
Correct |
120 ms |
232528 KB |
Output is correct |
28 |
Correct |
100 ms |
232560 KB |
Output is correct |
29 |
Correct |
102 ms |
232528 KB |
Output is correct |
30 |
Correct |
113 ms |
232532 KB |
Output is correct |
31 |
Correct |
101 ms |
232320 KB |
Output is correct |
32 |
Correct |
99 ms |
232276 KB |
Output is correct |
33 |
Correct |
116 ms |
232360 KB |
Output is correct |
34 |
Correct |
112 ms |
232300 KB |
Output is correct |
35 |
Correct |
98 ms |
232220 KB |
Output is correct |
36 |
Correct |
114 ms |
232396 KB |
Output is correct |
37 |
Correct |
99 ms |
232532 KB |
Output is correct |
38 |
Correct |
103 ms |
232564 KB |
Output is correct |
39 |
Correct |
102 ms |
232540 KB |
Output is correct |
40 |
Correct |
101 ms |
232272 KB |
Output is correct |
41 |
Correct |
102 ms |
232252 KB |
Output is correct |
42 |
Correct |
344 ms |
260940 KB |
Output is correct |
43 |
Correct |
444 ms |
275680 KB |
Output is correct |
44 |
Correct |
145 ms |
239124 KB |
Output is correct |
45 |
Correct |
394 ms |
265892 KB |
Output is correct |
46 |
Correct |
318 ms |
272372 KB |
Output is correct |
47 |
Correct |
97 ms |
232016 KB |
Output is correct |
48 |
Correct |
112 ms |
232128 KB |
Output is correct |
49 |
Correct |
107 ms |
232420 KB |
Output is correct |
50 |
Correct |
284 ms |
274884 KB |
Output is correct |
51 |
Correct |
311 ms |
274736 KB |
Output is correct |
52 |
Correct |
356 ms |
263432 KB |
Output is correct |
53 |
Correct |
353 ms |
263380 KB |
Output is correct |
54 |
Correct |
374 ms |
263332 KB |
Output is correct |
55 |
Correct |
353 ms |
262728 KB |
Output is correct |
56 |
Correct |
432 ms |
276360 KB |
Output is correct |
57 |
Correct |
356 ms |
279416 KB |
Output is correct |
58 |
Correct |
383 ms |
280252 KB |
Output is correct |
59 |
Correct |
609 ms |
274700 KB |
Output is correct |
60 |
Correct |
506 ms |
268040 KB |
Output is correct |
61 |
Correct |
586 ms |
276472 KB |
Output is correct |
62 |
Correct |
586 ms |
297712 KB |
Output is correct |
63 |
Correct |
293 ms |
269972 KB |
Output is correct |
64 |
Correct |
100 ms |
232852 KB |
Output is correct |
65 |
Correct |
102 ms |
232960 KB |
Output is correct |
66 |
Correct |
601 ms |
298096 KB |
Output is correct |
67 |
Correct |
120 ms |
236372 KB |
Output is correct |
68 |
Correct |
125 ms |
239032 KB |
Output is correct |
69 |
Correct |
570 ms |
273832 KB |
Output is correct |
70 |
Correct |
157 ms |
245840 KB |
Output is correct |
71 |
Correct |
277 ms |
273132 KB |
Output is correct |
72 |
Correct |
586 ms |
273892 KB |
Output is correct |
73 |
Correct |
580 ms |
298880 KB |
Output is correct |