# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
568368 |
2022-05-25T09:18:36 Z |
kartel |
Keys (IOI21_keys) |
C++17 |
|
1028 ms |
142628 KB |
#include <bits/stdc++.h>
//#include "grader.cpp"
#include "keys.h"
#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#define el "\n"
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int N = 3e5 + 500;
vector <pair <int, int> > g[N];
set <int> unlocked[N], colors[N];
set <pair <int, int> > locked[N];
int pr[N], prc[N], cnt[N];
int mk[N], to[N];
int n, m, root[N];
bool answer[N];
vector <int> r;
void get(int c, int u) {
while (1) {
auto it = locked[u].lower_bound(make_pair(c, -1));
if (it == locked[u].end() || it -> F != c) {
break;
}
unlocked[u].insert(it -> S);
locked[u].erase(it);
}
}
int fc(int v) {return (prc[v] == v ? v : prc[v] = fc(prc[v]));}
void link_cyc(int v, int u) {
v = fc(v); u = fc(u);
if (v == u) {
return;
}
if (sz(unlocked[v]) + sz(locked[v]) + sz(colors[v]) > sz(unlocked[u]) + sz(locked[u]) + sz(colors[u])) {
swap(u, v);
}
for (auto x : unlocked[v]) {
unlocked[u].insert(x);
}
for (auto x : locked[v]) {
if (colors[u].count(x.F)) {
unlocked[u].insert(x.S);
} else {
locked[u].insert(x);
}
}
for (auto x : colors[v]) {
if (!colors[u].count(x)) {
colors[u].insert(x);
get(x, u);
}
}
prc[v] = u;
cnt[u] += cnt[v];
}
int f(int v) {return (pr[v] == v ? v : pr[v] = f(pr[v]));}
void link(int v, int u) {
v = f(v); u = f(u);
if (v == u) {
return;
}
pr[v] = u;
}
void go(int c) {
int v = root[c], rt = root[c];
while (!mk[v]) {
mk[v] = 1;
link_cyc(v, to[v]);
v = to[v];
}
while (sz(unlocked[fc(rt)])) {
int u = fc(*unlocked[fc(rt)].begin());
unlocked[fc(rt)].erase(unlocked[fc(rt)].begin());
if (u == fc(rt)) {
continue;
}
if (f(u) != f(rt)) {
answer[c] = 0;
mk[fc(rt)] = 0;
to[fc(rt)] = u;
link(u, rt);
break;
}
while (!mk[u]) {
mk[u] = 1;
link_cyc(u, rt);
u = to[u];
}
}
}
vector <int> find_reachable(vector <int> _r, vector <int> u, vector <int> v, vector <int> c) {
r = _r;
n = sz(r); m = sz(u);
for (int i = 0; i < m; i++) {
g[u[i]].pb({v[i], c[i]});
g[v[i]].pb({u[i], c[i]});
}
vector <int> ans(n, 0);
bool ret = 0;
for (int i = 0; i < n; i++) {
to[i] = -1;
prc[i] = i; cnt[i] = 1;
pr[i] = i;
colors[i].insert(r[i]);
for (auto [u, c] : g[i]) {
if (r[i] == c) {
to[i] = u;
unlocked[i].insert(u);
} else {
locked[i].insert({c, u});
}
}
if (to[i] == -1) {
ans[i] = 1;
ret = 1;
}
}
if (ret) {
return ans;
}
int cmp = 0;
for (int i = 0; i < n; i++) {
if (mk[i]) {
continue;
}
vector <int> nodes;
int v = i;
while (!mk[v]) {
mk[v] = 1;
nodes.pb(v);
link(v, to[v]);
v = to[v];
}
if (mk[v] == 1) {
root[cmp] = v;
cmp++;
}
for (auto v : nodes) {
mk[v] = 2;
}
}
for (int i = 0; i < n; i++) {
mk[i] = 0;
}
for (int i = 0; i < cmp; i++) {
answer[i] = 1;
go(i);
}
int mn = 1e9;
for (int i = 0; i < cmp; i++) {
if (!answer[i]) {
continue;
}
mn = min(mn, cnt[fc(root[i])]);
}
set <int> cmps;
for (int i = 0; i < cmp; i++) {
if (answer[i] && cnt[fc(root[i])] == mn) {
cmps.insert(fc(root[i]));
}
}
for (int i = 0; i < n; i++) {
if (cmps.count(fc(i))) {
ans[i] = 1;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
49688 KB |
Output is correct |
2 |
Correct |
31 ms |
49688 KB |
Output is correct |
3 |
Correct |
29 ms |
49688 KB |
Output is correct |
4 |
Correct |
29 ms |
49636 KB |
Output is correct |
5 |
Correct |
28 ms |
49748 KB |
Output is correct |
6 |
Correct |
29 ms |
49748 KB |
Output is correct |
7 |
Correct |
30 ms |
49660 KB |
Output is correct |
8 |
Correct |
32 ms |
49688 KB |
Output is correct |
9 |
Correct |
33 ms |
49684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
49688 KB |
Output is correct |
2 |
Correct |
31 ms |
49688 KB |
Output is correct |
3 |
Correct |
29 ms |
49688 KB |
Output is correct |
4 |
Correct |
29 ms |
49636 KB |
Output is correct |
5 |
Correct |
28 ms |
49748 KB |
Output is correct |
6 |
Correct |
29 ms |
49748 KB |
Output is correct |
7 |
Correct |
30 ms |
49660 KB |
Output is correct |
8 |
Correct |
32 ms |
49688 KB |
Output is correct |
9 |
Correct |
33 ms |
49684 KB |
Output is correct |
10 |
Correct |
30 ms |
49780 KB |
Output is correct |
11 |
Correct |
27 ms |
49696 KB |
Output is correct |
12 |
Correct |
28 ms |
49748 KB |
Output is correct |
13 |
Correct |
25 ms |
49640 KB |
Output is correct |
14 |
Correct |
26 ms |
49708 KB |
Output is correct |
15 |
Correct |
29 ms |
49704 KB |
Output is correct |
16 |
Correct |
25 ms |
49684 KB |
Output is correct |
17 |
Correct |
31 ms |
49728 KB |
Output is correct |
18 |
Correct |
26 ms |
49700 KB |
Output is correct |
19 |
Correct |
32 ms |
49632 KB |
Output is correct |
20 |
Correct |
29 ms |
49688 KB |
Output is correct |
21 |
Correct |
27 ms |
49748 KB |
Output is correct |
22 |
Correct |
29 ms |
49664 KB |
Output is correct |
23 |
Correct |
25 ms |
49708 KB |
Output is correct |
24 |
Correct |
25 ms |
49744 KB |
Output is correct |
25 |
Correct |
30 ms |
49660 KB |
Output is correct |
26 |
Correct |
29 ms |
49748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
49688 KB |
Output is correct |
2 |
Correct |
31 ms |
49688 KB |
Output is correct |
3 |
Correct |
29 ms |
49688 KB |
Output is correct |
4 |
Correct |
29 ms |
49636 KB |
Output is correct |
5 |
Correct |
28 ms |
49748 KB |
Output is correct |
6 |
Correct |
29 ms |
49748 KB |
Output is correct |
7 |
Correct |
30 ms |
49660 KB |
Output is correct |
8 |
Correct |
32 ms |
49688 KB |
Output is correct |
9 |
Correct |
33 ms |
49684 KB |
Output is correct |
10 |
Correct |
30 ms |
49780 KB |
Output is correct |
11 |
Correct |
27 ms |
49696 KB |
Output is correct |
12 |
Correct |
28 ms |
49748 KB |
Output is correct |
13 |
Correct |
25 ms |
49640 KB |
Output is correct |
14 |
Correct |
26 ms |
49708 KB |
Output is correct |
15 |
Correct |
29 ms |
49704 KB |
Output is correct |
16 |
Correct |
25 ms |
49684 KB |
Output is correct |
17 |
Correct |
31 ms |
49728 KB |
Output is correct |
18 |
Correct |
26 ms |
49700 KB |
Output is correct |
19 |
Correct |
32 ms |
49632 KB |
Output is correct |
20 |
Correct |
29 ms |
49688 KB |
Output is correct |
21 |
Correct |
27 ms |
49748 KB |
Output is correct |
22 |
Correct |
29 ms |
49664 KB |
Output is correct |
23 |
Correct |
25 ms |
49708 KB |
Output is correct |
24 |
Correct |
25 ms |
49744 KB |
Output is correct |
25 |
Correct |
30 ms |
49660 KB |
Output is correct |
26 |
Correct |
29 ms |
49748 KB |
Output is correct |
27 |
Correct |
28 ms |
50168 KB |
Output is correct |
28 |
Correct |
27 ms |
50128 KB |
Output is correct |
29 |
Correct |
30 ms |
50132 KB |
Output is correct |
30 |
Correct |
28 ms |
50016 KB |
Output is correct |
31 |
Correct |
26 ms |
49844 KB |
Output is correct |
32 |
Correct |
25 ms |
49792 KB |
Output is correct |
33 |
Correct |
26 ms |
49840 KB |
Output is correct |
34 |
Correct |
26 ms |
49952 KB |
Output is correct |
35 |
Correct |
26 ms |
49948 KB |
Output is correct |
36 |
Correct |
31 ms |
50124 KB |
Output is correct |
37 |
Correct |
31 ms |
50084 KB |
Output is correct |
38 |
Correct |
33 ms |
50144 KB |
Output is correct |
39 |
Correct |
28 ms |
50168 KB |
Output is correct |
40 |
Correct |
31 ms |
49996 KB |
Output is correct |
41 |
Correct |
25 ms |
50184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
49688 KB |
Output is correct |
2 |
Correct |
31 ms |
49688 KB |
Output is correct |
3 |
Correct |
29 ms |
49688 KB |
Output is correct |
4 |
Correct |
29 ms |
49636 KB |
Output is correct |
5 |
Correct |
28 ms |
49748 KB |
Output is correct |
6 |
Correct |
29 ms |
49748 KB |
Output is correct |
7 |
Correct |
30 ms |
49660 KB |
Output is correct |
8 |
Correct |
32 ms |
49688 KB |
Output is correct |
9 |
Correct |
33 ms |
49684 KB |
Output is correct |
10 |
Correct |
275 ms |
101004 KB |
Output is correct |
11 |
Correct |
657 ms |
121480 KB |
Output is correct |
12 |
Correct |
116 ms |
65056 KB |
Output is correct |
13 |
Correct |
592 ms |
123580 KB |
Output is correct |
14 |
Correct |
383 ms |
142136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
49688 KB |
Output is correct |
2 |
Correct |
31 ms |
49688 KB |
Output is correct |
3 |
Correct |
29 ms |
49688 KB |
Output is correct |
4 |
Correct |
29 ms |
49636 KB |
Output is correct |
5 |
Correct |
28 ms |
49748 KB |
Output is correct |
6 |
Correct |
29 ms |
49748 KB |
Output is correct |
7 |
Correct |
30 ms |
49660 KB |
Output is correct |
8 |
Correct |
32 ms |
49688 KB |
Output is correct |
9 |
Correct |
33 ms |
49684 KB |
Output is correct |
10 |
Correct |
30 ms |
49780 KB |
Output is correct |
11 |
Correct |
27 ms |
49696 KB |
Output is correct |
12 |
Correct |
28 ms |
49748 KB |
Output is correct |
13 |
Correct |
25 ms |
49640 KB |
Output is correct |
14 |
Correct |
26 ms |
49708 KB |
Output is correct |
15 |
Correct |
29 ms |
49704 KB |
Output is correct |
16 |
Correct |
25 ms |
49684 KB |
Output is correct |
17 |
Correct |
31 ms |
49728 KB |
Output is correct |
18 |
Correct |
26 ms |
49700 KB |
Output is correct |
19 |
Correct |
32 ms |
49632 KB |
Output is correct |
20 |
Correct |
29 ms |
49688 KB |
Output is correct |
21 |
Correct |
27 ms |
49748 KB |
Output is correct |
22 |
Correct |
29 ms |
49664 KB |
Output is correct |
23 |
Correct |
25 ms |
49708 KB |
Output is correct |
24 |
Correct |
25 ms |
49744 KB |
Output is correct |
25 |
Correct |
30 ms |
49660 KB |
Output is correct |
26 |
Correct |
29 ms |
49748 KB |
Output is correct |
27 |
Correct |
28 ms |
50168 KB |
Output is correct |
28 |
Correct |
27 ms |
50128 KB |
Output is correct |
29 |
Correct |
30 ms |
50132 KB |
Output is correct |
30 |
Correct |
28 ms |
50016 KB |
Output is correct |
31 |
Correct |
26 ms |
49844 KB |
Output is correct |
32 |
Correct |
25 ms |
49792 KB |
Output is correct |
33 |
Correct |
26 ms |
49840 KB |
Output is correct |
34 |
Correct |
26 ms |
49952 KB |
Output is correct |
35 |
Correct |
26 ms |
49948 KB |
Output is correct |
36 |
Correct |
31 ms |
50124 KB |
Output is correct |
37 |
Correct |
31 ms |
50084 KB |
Output is correct |
38 |
Correct |
33 ms |
50144 KB |
Output is correct |
39 |
Correct |
28 ms |
50168 KB |
Output is correct |
40 |
Correct |
31 ms |
49996 KB |
Output is correct |
41 |
Correct |
25 ms |
50184 KB |
Output is correct |
42 |
Correct |
275 ms |
101004 KB |
Output is correct |
43 |
Correct |
657 ms |
121480 KB |
Output is correct |
44 |
Correct |
116 ms |
65056 KB |
Output is correct |
45 |
Correct |
592 ms |
123580 KB |
Output is correct |
46 |
Correct |
383 ms |
142136 KB |
Output is correct |
47 |
Correct |
28 ms |
49724 KB |
Output is correct |
48 |
Correct |
27 ms |
49624 KB |
Output is correct |
49 |
Correct |
26 ms |
49696 KB |
Output is correct |
50 |
Correct |
462 ms |
140392 KB |
Output is correct |
51 |
Correct |
256 ms |
125948 KB |
Output is correct |
52 |
Correct |
256 ms |
102476 KB |
Output is correct |
53 |
Correct |
228 ms |
102492 KB |
Output is correct |
54 |
Correct |
233 ms |
102396 KB |
Output is correct |
55 |
Correct |
293 ms |
106664 KB |
Output is correct |
56 |
Correct |
375 ms |
127888 KB |
Output is correct |
57 |
Correct |
444 ms |
128076 KB |
Output is correct |
58 |
Correct |
446 ms |
128008 KB |
Output is correct |
59 |
Correct |
1020 ms |
137980 KB |
Output is correct |
60 |
Correct |
361 ms |
117092 KB |
Output is correct |
61 |
Correct |
323 ms |
117324 KB |
Output is correct |
62 |
Correct |
298 ms |
110116 KB |
Output is correct |
63 |
Correct |
292 ms |
115004 KB |
Output is correct |
64 |
Correct |
34 ms |
51260 KB |
Output is correct |
65 |
Correct |
32 ms |
51176 KB |
Output is correct |
66 |
Correct |
296 ms |
110132 KB |
Output is correct |
67 |
Correct |
60 ms |
58964 KB |
Output is correct |
68 |
Correct |
78 ms |
65116 KB |
Output is correct |
69 |
Correct |
1028 ms |
138200 KB |
Output is correct |
70 |
Correct |
136 ms |
80552 KB |
Output is correct |
71 |
Correct |
336 ms |
142628 KB |
Output is correct |
72 |
Correct |
1008 ms |
138180 KB |
Output is correct |
73 |
Correct |
268 ms |
110000 KB |
Output is correct |