# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
768907 |
2023-06-28T21:10:47 Z |
PurpleCrayon |
Keys (IOI21_keys) |
C++17 |
|
1348 ms |
194780 KB |
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;
struct DSU {
vector<int> par, sz;
DSU(int n): par(n) {
iota(par.begin(), par.end(), 0);
sz.assign(n, 1);
}
int find_set(int v) {
return v == par[v] ? v : par[v] = find_set(par[v]);
}
bool union_sets(int a, int b) {
if ((a = find_set(a)) == (b = find_set(b))) return false;
if (sz[a] < sz[b]) swap(a, b);
par[b] = a, sz[a] += sz[b], sz[b] = 0;
return true;
}
};
int n, m, my_out[N];
int par[N];
vector<int> st[N];
set<int> has[N];
map<int, vector<int>> by_col[N];
set<int> both[N];
vector<ar<int, 2>> adj[N];
void merge(int a, int b) {
a = par[a], b = par[b];
if (a == b) return;
if (sz(st[a]) < sz(st[b])) swap(a, b);
for (int x : st[b]) {
st[a].push_back(x);
par[x] = a;
}
st[b].clear();
for (int x : has[b]) {
has[a].insert(x);
if (sz(by_col[a][x])) {
both[a].insert(x);
}
}
has[b].clear();
for (auto [x, v] : by_col[b]) {
if (!sz(v)) continue;
vector<int>& base = by_col[a][x];
for (int y : v) {
base.push_back(y);
}
if (has[a].count(x)) {
both[a].insert(x);
}
}
by_col[b].clear();
both[b].clear();
}
int get_out(int c) {
c = par[c];
int ans = -1;
vector<int> done;
for (int x : both[c]) {
vector<int>& v = by_col[c][x];
while (sz(v)) {
if (par[v.back()] == c) {
v.pop_back();
} else {
ans = par[v.back()];
goto found;
}
}
done.push_back(x);
}
found:
for (int x : done) both[c].erase(x);
return ans;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = sz(r), m = sz(u);
memset(my_out, -1, sizeof(my_out));
for (int i = 0; i < n; i++) {
par[i] = i;
st[i].push_back(i);
has[i].insert(r[i]);
}
for (int i = 0; i < m; i++) {
adj[u[i]].push_back({v[i], c[i]});
adj[v[i]].push_back({u[i], c[i]});
}
for (int i = 0; i < n; i++) {
for (auto [nxt, w] : adj[i]) {
by_col[i][w].push_back(nxt);
}
for (int x : has[i]) if (sz(by_col[i][x])) {
both[i].insert(x);
}
}
DSU d(n);
for (int root = 0; root < n; root++) {
my_out[par[root]] = get_out(root);
while (my_out[par[root]] != -1) {
if (d.union_sets(root, my_out[par[root]])) {
break;
} else {
vector<int> use{par[my_out[par[root]]]};
while (use.back() != par[root]) {
use.push_back(par[my_out[use.back()]]);
}
use.pop_back();
for (int x : use) {
merge(x, root);
}
my_out[par[root]] = get_out(root);
}
}
}
int best = MOD;
for (int i = 0; i < n; i++) {
int c = par[i];
if (my_out[c] == -1) {
best = min(best, sz(st[c]));
}
}
vector<int> ans(n);
for (int i = 0; i < n; i++) {
int c = par[i];
if (my_out[c] == -1 && sz(st[c]) == best) {
ans[i] = 1;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57812 KB |
Output is correct |
2 |
Correct |
23 ms |
57812 KB |
Output is correct |
3 |
Correct |
23 ms |
57812 KB |
Output is correct |
4 |
Correct |
24 ms |
57840 KB |
Output is correct |
5 |
Correct |
23 ms |
57820 KB |
Output is correct |
6 |
Correct |
23 ms |
57812 KB |
Output is correct |
7 |
Correct |
23 ms |
57808 KB |
Output is correct |
8 |
Correct |
24 ms |
57800 KB |
Output is correct |
9 |
Correct |
23 ms |
57940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57812 KB |
Output is correct |
2 |
Correct |
23 ms |
57812 KB |
Output is correct |
3 |
Correct |
23 ms |
57812 KB |
Output is correct |
4 |
Correct |
24 ms |
57840 KB |
Output is correct |
5 |
Correct |
23 ms |
57820 KB |
Output is correct |
6 |
Correct |
23 ms |
57812 KB |
Output is correct |
7 |
Correct |
23 ms |
57808 KB |
Output is correct |
8 |
Correct |
24 ms |
57800 KB |
Output is correct |
9 |
Correct |
23 ms |
57940 KB |
Output is correct |
10 |
Correct |
24 ms |
57832 KB |
Output is correct |
11 |
Correct |
22 ms |
57888 KB |
Output is correct |
12 |
Correct |
21 ms |
57824 KB |
Output is correct |
13 |
Correct |
24 ms |
57824 KB |
Output is correct |
14 |
Correct |
24 ms |
57740 KB |
Output is correct |
15 |
Correct |
25 ms |
57820 KB |
Output is correct |
16 |
Correct |
23 ms |
57824 KB |
Output is correct |
17 |
Correct |
23 ms |
57808 KB |
Output is correct |
18 |
Correct |
23 ms |
57800 KB |
Output is correct |
19 |
Correct |
23 ms |
57804 KB |
Output is correct |
20 |
Correct |
24 ms |
57736 KB |
Output is correct |
21 |
Correct |
24 ms |
57812 KB |
Output is correct |
22 |
Correct |
24 ms |
57820 KB |
Output is correct |
23 |
Correct |
24 ms |
57848 KB |
Output is correct |
24 |
Correct |
23 ms |
57824 KB |
Output is correct |
25 |
Correct |
28 ms |
57948 KB |
Output is correct |
26 |
Correct |
23 ms |
57840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57812 KB |
Output is correct |
2 |
Correct |
23 ms |
57812 KB |
Output is correct |
3 |
Correct |
23 ms |
57812 KB |
Output is correct |
4 |
Correct |
24 ms |
57840 KB |
Output is correct |
5 |
Correct |
23 ms |
57820 KB |
Output is correct |
6 |
Correct |
23 ms |
57812 KB |
Output is correct |
7 |
Correct |
23 ms |
57808 KB |
Output is correct |
8 |
Correct |
24 ms |
57800 KB |
Output is correct |
9 |
Correct |
23 ms |
57940 KB |
Output is correct |
10 |
Correct |
24 ms |
57832 KB |
Output is correct |
11 |
Correct |
22 ms |
57888 KB |
Output is correct |
12 |
Correct |
21 ms |
57824 KB |
Output is correct |
13 |
Correct |
24 ms |
57824 KB |
Output is correct |
14 |
Correct |
24 ms |
57740 KB |
Output is correct |
15 |
Correct |
25 ms |
57820 KB |
Output is correct |
16 |
Correct |
23 ms |
57824 KB |
Output is correct |
17 |
Correct |
23 ms |
57808 KB |
Output is correct |
18 |
Correct |
23 ms |
57800 KB |
Output is correct |
19 |
Correct |
23 ms |
57804 KB |
Output is correct |
20 |
Correct |
24 ms |
57736 KB |
Output is correct |
21 |
Correct |
24 ms |
57812 KB |
Output is correct |
22 |
Correct |
24 ms |
57820 KB |
Output is correct |
23 |
Correct |
24 ms |
57848 KB |
Output is correct |
24 |
Correct |
23 ms |
57824 KB |
Output is correct |
25 |
Correct |
28 ms |
57948 KB |
Output is correct |
26 |
Correct |
23 ms |
57840 KB |
Output is correct |
27 |
Correct |
26 ms |
58728 KB |
Output is correct |
28 |
Correct |
25 ms |
58644 KB |
Output is correct |
29 |
Correct |
25 ms |
58716 KB |
Output is correct |
30 |
Correct |
25 ms |
58240 KB |
Output is correct |
31 |
Correct |
27 ms |
58092 KB |
Output is correct |
32 |
Correct |
26 ms |
57912 KB |
Output is correct |
33 |
Correct |
25 ms |
58224 KB |
Output is correct |
34 |
Correct |
25 ms |
58188 KB |
Output is correct |
35 |
Correct |
25 ms |
58196 KB |
Output is correct |
36 |
Correct |
30 ms |
58584 KB |
Output is correct |
37 |
Correct |
26 ms |
58560 KB |
Output is correct |
38 |
Correct |
27 ms |
58700 KB |
Output is correct |
39 |
Correct |
28 ms |
58712 KB |
Output is correct |
40 |
Correct |
25 ms |
58216 KB |
Output is correct |
41 |
Correct |
26 ms |
58448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57812 KB |
Output is correct |
2 |
Correct |
23 ms |
57812 KB |
Output is correct |
3 |
Correct |
23 ms |
57812 KB |
Output is correct |
4 |
Correct |
24 ms |
57840 KB |
Output is correct |
5 |
Correct |
23 ms |
57820 KB |
Output is correct |
6 |
Correct |
23 ms |
57812 KB |
Output is correct |
7 |
Correct |
23 ms |
57808 KB |
Output is correct |
8 |
Correct |
24 ms |
57800 KB |
Output is correct |
9 |
Correct |
23 ms |
57940 KB |
Output is correct |
10 |
Correct |
411 ms |
142444 KB |
Output is correct |
11 |
Correct |
564 ms |
158536 KB |
Output is correct |
12 |
Correct |
121 ms |
81632 KB |
Output is correct |
13 |
Correct |
642 ms |
173780 KB |
Output is correct |
14 |
Correct |
253 ms |
153280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
57812 KB |
Output is correct |
2 |
Correct |
23 ms |
57812 KB |
Output is correct |
3 |
Correct |
23 ms |
57812 KB |
Output is correct |
4 |
Correct |
24 ms |
57840 KB |
Output is correct |
5 |
Correct |
23 ms |
57820 KB |
Output is correct |
6 |
Correct |
23 ms |
57812 KB |
Output is correct |
7 |
Correct |
23 ms |
57808 KB |
Output is correct |
8 |
Correct |
24 ms |
57800 KB |
Output is correct |
9 |
Correct |
23 ms |
57940 KB |
Output is correct |
10 |
Correct |
24 ms |
57832 KB |
Output is correct |
11 |
Correct |
22 ms |
57888 KB |
Output is correct |
12 |
Correct |
21 ms |
57824 KB |
Output is correct |
13 |
Correct |
24 ms |
57824 KB |
Output is correct |
14 |
Correct |
24 ms |
57740 KB |
Output is correct |
15 |
Correct |
25 ms |
57820 KB |
Output is correct |
16 |
Correct |
23 ms |
57824 KB |
Output is correct |
17 |
Correct |
23 ms |
57808 KB |
Output is correct |
18 |
Correct |
23 ms |
57800 KB |
Output is correct |
19 |
Correct |
23 ms |
57804 KB |
Output is correct |
20 |
Correct |
24 ms |
57736 KB |
Output is correct |
21 |
Correct |
24 ms |
57812 KB |
Output is correct |
22 |
Correct |
24 ms |
57820 KB |
Output is correct |
23 |
Correct |
24 ms |
57848 KB |
Output is correct |
24 |
Correct |
23 ms |
57824 KB |
Output is correct |
25 |
Correct |
28 ms |
57948 KB |
Output is correct |
26 |
Correct |
23 ms |
57840 KB |
Output is correct |
27 |
Correct |
26 ms |
58728 KB |
Output is correct |
28 |
Correct |
25 ms |
58644 KB |
Output is correct |
29 |
Correct |
25 ms |
58716 KB |
Output is correct |
30 |
Correct |
25 ms |
58240 KB |
Output is correct |
31 |
Correct |
27 ms |
58092 KB |
Output is correct |
32 |
Correct |
26 ms |
57912 KB |
Output is correct |
33 |
Correct |
25 ms |
58224 KB |
Output is correct |
34 |
Correct |
25 ms |
58188 KB |
Output is correct |
35 |
Correct |
25 ms |
58196 KB |
Output is correct |
36 |
Correct |
30 ms |
58584 KB |
Output is correct |
37 |
Correct |
26 ms |
58560 KB |
Output is correct |
38 |
Correct |
27 ms |
58700 KB |
Output is correct |
39 |
Correct |
28 ms |
58712 KB |
Output is correct |
40 |
Correct |
25 ms |
58216 KB |
Output is correct |
41 |
Correct |
26 ms |
58448 KB |
Output is correct |
42 |
Correct |
411 ms |
142444 KB |
Output is correct |
43 |
Correct |
564 ms |
158536 KB |
Output is correct |
44 |
Correct |
121 ms |
81632 KB |
Output is correct |
45 |
Correct |
642 ms |
173780 KB |
Output is correct |
46 |
Correct |
253 ms |
153280 KB |
Output is correct |
47 |
Correct |
23 ms |
57812 KB |
Output is correct |
48 |
Correct |
22 ms |
57780 KB |
Output is correct |
49 |
Correct |
24 ms |
57724 KB |
Output is correct |
50 |
Correct |
245 ms |
158400 KB |
Output is correct |
51 |
Correct |
270 ms |
154780 KB |
Output is correct |
52 |
Correct |
225 ms |
147404 KB |
Output is correct |
53 |
Correct |
231 ms |
147384 KB |
Output is correct |
54 |
Correct |
230 ms |
147360 KB |
Output is correct |
55 |
Correct |
582 ms |
149648 KB |
Output is correct |
56 |
Correct |
305 ms |
180776 KB |
Output is correct |
57 |
Correct |
264 ms |
172640 KB |
Output is correct |
58 |
Correct |
418 ms |
194780 KB |
Output is correct |
59 |
Correct |
1226 ms |
177992 KB |
Output is correct |
60 |
Correct |
292 ms |
167972 KB |
Output is correct |
61 |
Correct |
1195 ms |
171364 KB |
Output is correct |
62 |
Correct |
1348 ms |
159316 KB |
Output is correct |
63 |
Correct |
356 ms |
159844 KB |
Output is correct |
64 |
Correct |
30 ms |
59516 KB |
Output is correct |
65 |
Correct |
29 ms |
59604 KB |
Output is correct |
66 |
Correct |
1334 ms |
158800 KB |
Output is correct |
67 |
Correct |
49 ms |
68044 KB |
Output is correct |
68 |
Correct |
65 ms |
74792 KB |
Output is correct |
69 |
Correct |
1235 ms |
177952 KB |
Output is correct |
70 |
Correct |
106 ms |
91716 KB |
Output is correct |
71 |
Correct |
264 ms |
160736 KB |
Output is correct |
72 |
Correct |
1222 ms |
178140 KB |
Output is correct |
73 |
Correct |
1331 ms |
158956 KB |
Output is correct |