# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
828788 |
2023-08-17T16:12:18 Z |
fatemetmhr |
Keys (IOI21_keys) |
C++17 |
|
1712 ms |
216760 KB |
// Be Name Khoda //
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int maxn5 = 3e5 + 10;
set <int> key[maxn5];
set <pair<int, int>> ed[maxn5];
vector <int> edge[maxn5], av[maxn5];
vector <pair<int, int>> adj[maxn5];
int cmp[maxn5], r[maxn5], mark[maxn5];
bool bad[maxn5];
int merge(int a, int b){
if(av[a].size() < av[b].size())
swap(a, b);
//cout << "here merging " << a << ' ' << b << endl;
for(auto u : av[b]){
cmp[u] = a;
av[a].pb(u);
key[r[u]].insert(a);
for(auto it = ed[r[u]].lower_bound(mp(a, -1)); it != ed[r[u]].end() && (it -> fi) == a;){
auto itt = it;
it++;
edge[a].pb(itt -> se);
ed[r[u]].erase(itt);
}
for(auto [v, c] : adj[u]){
if(key[c].find(a) != key[c].end())
edge[a].pb(v);
else
ed[c].insert({a, v});
}
}
av[b].clear();
av[b].shrink_to_fit();
return a;
}
bool dfs(int v){
mark[v] = 1;
//debug(v);
while(edge[v].size()){
int u = edge[v].back();
u = cmp[u];
//cout << "here is " << v << ' ' << u << ' ' << mark[u] << endl;
edge[v].pop_back();
if(u == v)
continue;
if(mark[u] == 0){
if(dfs(u)){
v = merge(v, cmp[u]);
mark[v] = 1;
}
else{
bad[v] = true;
mark[v] = 2;
return false;
}
}
else if(mark[u] == 1){
edge[v].pb(u);
return true;
}
else{
bad[v] = true;
mark[v] = 2;
return false;
}
}
mark[v] = 2;
return false;
}
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();
for(int i = 0; i < n; i++){
r[i] = R[i];
key[r[i]].insert(i);
cmp[i] = i;
av[i].pb(i);
}
for(int i = 0; i < int(u.size()); i++){
adj[u[i]].pb({v[i], c[i]});
adj[v[i]].pb({u[i], c[i]});
if(r[u[i]] == c[i])
edge[u[i]].pb(v[i]);
if(r[v[i]] == c[i])
edge[v[i]].pb(u[i]);
ed[c[i]].insert({v[i], u[i]});
ed[c[i]].insert({u[i], v[i]});
}
for(int i = 0; i < n; i++)
adj[i].shrink_to_fit();
for(int i = 0; i < n; i++) if(!mark[i])
dfs(i);
int mn = n;
vector <int> good;
for(int i = 0; i < n; i++) if(cmp[i] == i && !bad[i]){
//cout << "ha " << i << ' ' << av[i].size() << endl;
if(int(av[i].size()) < mn){
good.clear();
good = av[i];
mn = av[i].size();
}
else if(int(av[i].size()) == mn)
for(auto u : av[i])
good.pb(u);
}
vector <int> ret;
ret.resize(n);
fill(all(ret), 0);
for(auto u : good)
ret[u] = true;
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
49600 KB |
Output is correct |
2 |
Correct |
21 ms |
49632 KB |
Output is correct |
3 |
Correct |
21 ms |
49576 KB |
Output is correct |
4 |
Correct |
21 ms |
49620 KB |
Output is correct |
5 |
Correct |
21 ms |
49568 KB |
Output is correct |
6 |
Correct |
21 ms |
49620 KB |
Output is correct |
7 |
Correct |
21 ms |
49644 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
21 ms |
49680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
49600 KB |
Output is correct |
2 |
Correct |
21 ms |
49632 KB |
Output is correct |
3 |
Correct |
21 ms |
49576 KB |
Output is correct |
4 |
Correct |
21 ms |
49620 KB |
Output is correct |
5 |
Correct |
21 ms |
49568 KB |
Output is correct |
6 |
Correct |
21 ms |
49620 KB |
Output is correct |
7 |
Correct |
21 ms |
49644 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
21 ms |
49680 KB |
Output is correct |
10 |
Correct |
21 ms |
49620 KB |
Output is correct |
11 |
Correct |
23 ms |
49692 KB |
Output is correct |
12 |
Correct |
20 ms |
49612 KB |
Output is correct |
13 |
Correct |
21 ms |
49540 KB |
Output is correct |
14 |
Correct |
21 ms |
49524 KB |
Output is correct |
15 |
Correct |
21 ms |
49620 KB |
Output is correct |
16 |
Correct |
22 ms |
49620 KB |
Output is correct |
17 |
Correct |
21 ms |
49640 KB |
Output is correct |
18 |
Correct |
21 ms |
49636 KB |
Output is correct |
19 |
Correct |
21 ms |
49576 KB |
Output is correct |
20 |
Correct |
25 ms |
49620 KB |
Output is correct |
21 |
Correct |
21 ms |
49632 KB |
Output is correct |
22 |
Correct |
21 ms |
49588 KB |
Output is correct |
23 |
Correct |
21 ms |
49604 KB |
Output is correct |
24 |
Correct |
24 ms |
49648 KB |
Output is correct |
25 |
Correct |
21 ms |
49624 KB |
Output is correct |
26 |
Correct |
21 ms |
49688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
49600 KB |
Output is correct |
2 |
Correct |
21 ms |
49632 KB |
Output is correct |
3 |
Correct |
21 ms |
49576 KB |
Output is correct |
4 |
Correct |
21 ms |
49620 KB |
Output is correct |
5 |
Correct |
21 ms |
49568 KB |
Output is correct |
6 |
Correct |
21 ms |
49620 KB |
Output is correct |
7 |
Correct |
21 ms |
49644 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
21 ms |
49680 KB |
Output is correct |
10 |
Correct |
21 ms |
49620 KB |
Output is correct |
11 |
Correct |
23 ms |
49692 KB |
Output is correct |
12 |
Correct |
20 ms |
49612 KB |
Output is correct |
13 |
Correct |
21 ms |
49540 KB |
Output is correct |
14 |
Correct |
21 ms |
49524 KB |
Output is correct |
15 |
Correct |
21 ms |
49620 KB |
Output is correct |
16 |
Correct |
22 ms |
49620 KB |
Output is correct |
17 |
Correct |
21 ms |
49640 KB |
Output is correct |
18 |
Correct |
21 ms |
49636 KB |
Output is correct |
19 |
Correct |
21 ms |
49576 KB |
Output is correct |
20 |
Correct |
25 ms |
49620 KB |
Output is correct |
21 |
Correct |
21 ms |
49632 KB |
Output is correct |
22 |
Correct |
21 ms |
49588 KB |
Output is correct |
23 |
Correct |
21 ms |
49604 KB |
Output is correct |
24 |
Correct |
24 ms |
49648 KB |
Output is correct |
25 |
Correct |
21 ms |
49624 KB |
Output is correct |
26 |
Correct |
21 ms |
49688 KB |
Output is correct |
27 |
Correct |
23 ms |
50196 KB |
Output is correct |
28 |
Correct |
23 ms |
50220 KB |
Output is correct |
29 |
Correct |
22 ms |
50208 KB |
Output is correct |
30 |
Correct |
20 ms |
49960 KB |
Output is correct |
31 |
Correct |
23 ms |
49880 KB |
Output is correct |
32 |
Correct |
21 ms |
49748 KB |
Output is correct |
33 |
Correct |
22 ms |
49896 KB |
Output is correct |
34 |
Correct |
22 ms |
50028 KB |
Output is correct |
35 |
Correct |
27 ms |
49928 KB |
Output is correct |
36 |
Correct |
23 ms |
50260 KB |
Output is correct |
37 |
Correct |
25 ms |
50260 KB |
Output is correct |
38 |
Correct |
25 ms |
50336 KB |
Output is correct |
39 |
Correct |
23 ms |
50404 KB |
Output is correct |
40 |
Correct |
22 ms |
49916 KB |
Output is correct |
41 |
Correct |
23 ms |
50128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
49600 KB |
Output is correct |
2 |
Correct |
21 ms |
49632 KB |
Output is correct |
3 |
Correct |
21 ms |
49576 KB |
Output is correct |
4 |
Correct |
21 ms |
49620 KB |
Output is correct |
5 |
Correct |
21 ms |
49568 KB |
Output is correct |
6 |
Correct |
21 ms |
49620 KB |
Output is correct |
7 |
Correct |
21 ms |
49644 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
21 ms |
49680 KB |
Output is correct |
10 |
Correct |
734 ms |
117756 KB |
Output is correct |
11 |
Correct |
928 ms |
152844 KB |
Output is correct |
12 |
Correct |
147 ms |
68124 KB |
Output is correct |
13 |
Correct |
1196 ms |
140208 KB |
Output is correct |
14 |
Correct |
378 ms |
161540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
49600 KB |
Output is correct |
2 |
Correct |
21 ms |
49632 KB |
Output is correct |
3 |
Correct |
21 ms |
49576 KB |
Output is correct |
4 |
Correct |
21 ms |
49620 KB |
Output is correct |
5 |
Correct |
21 ms |
49568 KB |
Output is correct |
6 |
Correct |
21 ms |
49620 KB |
Output is correct |
7 |
Correct |
21 ms |
49644 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
21 ms |
49680 KB |
Output is correct |
10 |
Correct |
21 ms |
49620 KB |
Output is correct |
11 |
Correct |
23 ms |
49692 KB |
Output is correct |
12 |
Correct |
20 ms |
49612 KB |
Output is correct |
13 |
Correct |
21 ms |
49540 KB |
Output is correct |
14 |
Correct |
21 ms |
49524 KB |
Output is correct |
15 |
Correct |
21 ms |
49620 KB |
Output is correct |
16 |
Correct |
22 ms |
49620 KB |
Output is correct |
17 |
Correct |
21 ms |
49640 KB |
Output is correct |
18 |
Correct |
21 ms |
49636 KB |
Output is correct |
19 |
Correct |
21 ms |
49576 KB |
Output is correct |
20 |
Correct |
25 ms |
49620 KB |
Output is correct |
21 |
Correct |
21 ms |
49632 KB |
Output is correct |
22 |
Correct |
21 ms |
49588 KB |
Output is correct |
23 |
Correct |
21 ms |
49604 KB |
Output is correct |
24 |
Correct |
24 ms |
49648 KB |
Output is correct |
25 |
Correct |
21 ms |
49624 KB |
Output is correct |
26 |
Correct |
21 ms |
49688 KB |
Output is correct |
27 |
Correct |
23 ms |
50196 KB |
Output is correct |
28 |
Correct |
23 ms |
50220 KB |
Output is correct |
29 |
Correct |
22 ms |
50208 KB |
Output is correct |
30 |
Correct |
20 ms |
49960 KB |
Output is correct |
31 |
Correct |
23 ms |
49880 KB |
Output is correct |
32 |
Correct |
21 ms |
49748 KB |
Output is correct |
33 |
Correct |
22 ms |
49896 KB |
Output is correct |
34 |
Correct |
22 ms |
50028 KB |
Output is correct |
35 |
Correct |
27 ms |
49928 KB |
Output is correct |
36 |
Correct |
23 ms |
50260 KB |
Output is correct |
37 |
Correct |
25 ms |
50260 KB |
Output is correct |
38 |
Correct |
25 ms |
50336 KB |
Output is correct |
39 |
Correct |
23 ms |
50404 KB |
Output is correct |
40 |
Correct |
22 ms |
49916 KB |
Output is correct |
41 |
Correct |
23 ms |
50128 KB |
Output is correct |
42 |
Correct |
734 ms |
117756 KB |
Output is correct |
43 |
Correct |
928 ms |
152844 KB |
Output is correct |
44 |
Correct |
147 ms |
68124 KB |
Output is correct |
45 |
Correct |
1196 ms |
140208 KB |
Output is correct |
46 |
Correct |
378 ms |
161540 KB |
Output is correct |
47 |
Correct |
21 ms |
49620 KB |
Output is correct |
48 |
Correct |
23 ms |
49624 KB |
Output is correct |
49 |
Correct |
21 ms |
49648 KB |
Output is correct |
50 |
Correct |
520 ms |
159420 KB |
Output is correct |
51 |
Correct |
436 ms |
146764 KB |
Output is correct |
52 |
Correct |
341 ms |
110408 KB |
Output is correct |
53 |
Correct |
298 ms |
110360 KB |
Output is correct |
54 |
Correct |
302 ms |
110420 KB |
Output is correct |
55 |
Correct |
575 ms |
121776 KB |
Output is correct |
56 |
Correct |
560 ms |
143728 KB |
Output is correct |
57 |
Correct |
622 ms |
138272 KB |
Output is correct |
58 |
Correct |
416 ms |
144564 KB |
Output is correct |
59 |
Correct |
741 ms |
149488 KB |
Output is correct |
60 |
Correct |
561 ms |
131924 KB |
Output is correct |
61 |
Correct |
918 ms |
155364 KB |
Output is correct |
62 |
Correct |
1669 ms |
216732 KB |
Output is correct |
63 |
Correct |
265 ms |
134492 KB |
Output is correct |
64 |
Correct |
29 ms |
51444 KB |
Output is correct |
65 |
Correct |
31 ms |
51592 KB |
Output is correct |
66 |
Correct |
1649 ms |
216760 KB |
Output is correct |
67 |
Correct |
48 ms |
60876 KB |
Output is correct |
68 |
Correct |
67 ms |
68284 KB |
Output is correct |
69 |
Correct |
723 ms |
149016 KB |
Output is correct |
70 |
Correct |
114 ms |
86760 KB |
Output is correct |
71 |
Correct |
309 ms |
161952 KB |
Output is correct |
72 |
Correct |
754 ms |
149048 KB |
Output is correct |
73 |
Correct |
1712 ms |
216644 KB |
Output is correct |