# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
827929 |
2023-08-16T22:53:31 Z |
Liudas |
Keys (IOI21_keys) |
C++17 |
|
253 ms |
84768 KB |
#include <bits/stdc++.h>
using namespace std;
template <int maxN>
struct dsu
{
int n, parents[maxN], rank[maxN];
void clear(int size)
{
n = size;
for (int i = 0; i < n; i++)
parents[i] = i;
memset(rank, 0, sizeof(int) * n);
}
int get(int a) { return parents[a] == a ? a : parents[a] = get(parents[a]); }
int merge(int a, int b)
{
if ((a = get(a)) == (b = get(b)))
return 0;
if (rank[a] < rank[b])
{
parents[a] = b;
}
else
{
parents[b] = a;
if (rank[a] == rank[b])
rank[a]++;
}
return 1;
}
};
dsu<300000> parent;
template <int maxN, int maxM>
struct graph
{
struct edge;
struct vertex
{
edge *next;
int visited, r;
} vs[maxN], *end = vs + maxN;
struct edge
{
vertex *to;
edge *next;
int c;
} es[maxM], *nextE = es;
void clear(int n) { memset(vs, 0, sizeof(vertex) * n), end = vs + n, nextE = es; }
edge *add(int from, int to) { return nextE->to = vs + to, nextE->next = vs[from].next, vs[from].next = nextE++; }
int round, min, reachSize, ans[maxN], ansSize, key[maxN], noKey[maxM], noKeySize;
vertex *reach[maxN];
vector<vertex *> noKeys[maxN];
vector<int> solve()
{
round = 0;
min = 0x3f3f3f3f;
ansSize = 0;
parent.clear(end - vs);
for (vertex *v = vs; v != end; v++)
{
for (int i = 0; i < reachSize; i++)
key[reach[i]->r] = 0;
for (int i = 0; i < noKeySize; i++)
noKeys[noKey[i]].clear();
reachSize = 0;
noKeySize = 0;
round++;
if (!dfs(v, v))
{
if (reachSize < min)
{
min = reachSize;
ansSize = 0;
}
if (reachSize == min)
for (int i = 0; i < reachSize; i++)
ans[ansSize++] = reach[i] - vs;
}
}
vector<int> ret(end - vs);
for (int i = 0; i < ansSize; i++)
ret[ans[i]] = 1;
return ret;
}
int dfs(vertex *v, vertex *start)
{
if (reachSize == min)
return 1;
reach[reachSize++] = v;
v->visited = round;
if (parent.merge(start - vs, v - vs))
return 1;
if (!key[v->r])
{
key[v->r] = 1;
for (vertex *u : noKeys[v->r])
if (u->visited < round)
if (dfs(u, start))
return 1;
}
for (edge *e = v->next; e; e = e->next)
if (e->to->visited < round)
{
if (key[e->c])
{
if (dfs(e->to, start))
return 1;
}
else
{
noKey[noKeySize++] = e->c;
noKeys[e->c].push_back(e->to);
}
}
return 0;
}
};
graph<300000, 2 * 300000> g;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
int n = r.size(), m = u.size();
g.clear(n);
for (int i = 0; i < n; i++)
g.vs[i].r = r[i];
for (int i = 0; i < m; i++)
{
g.add(u[i], v[i])->c = c[i];
g.add(v[i], u[i])->c = c[i];
}
return g.solve();
}
void testCase()
{
int n, m;
cin >> n >> m;
vector<int> r(n);
for (int i = 0; i < n; i++)
cin >> r[i];
vector<int> u(m), v(m), c(m);
for (int i = 0; i < m; i++)
cin >> u[i] >> v[i] >> c[i];
auto ans = find_reachable(r, u, v, c);
for (auto v : ans)
cout << v << ' ';
}
/*int main()
{
testCase();
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7380 KB |
Output is correct |
2 |
Correct |
3 ms |
7332 KB |
Output is correct |
3 |
Correct |
3 ms |
7380 KB |
Output is correct |
4 |
Correct |
3 ms |
7380 KB |
Output is correct |
5 |
Correct |
3 ms |
7380 KB |
Output is correct |
6 |
Correct |
3 ms |
7380 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7380 KB |
Output is correct |
9 |
Correct |
3 ms |
7380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7380 KB |
Output is correct |
2 |
Correct |
3 ms |
7332 KB |
Output is correct |
3 |
Correct |
3 ms |
7380 KB |
Output is correct |
4 |
Correct |
3 ms |
7380 KB |
Output is correct |
5 |
Correct |
3 ms |
7380 KB |
Output is correct |
6 |
Correct |
3 ms |
7380 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7380 KB |
Output is correct |
9 |
Correct |
3 ms |
7380 KB |
Output is correct |
10 |
Correct |
3 ms |
7380 KB |
Output is correct |
11 |
Correct |
3 ms |
7380 KB |
Output is correct |
12 |
Correct |
3 ms |
7380 KB |
Output is correct |
13 |
Correct |
3 ms |
7380 KB |
Output is correct |
14 |
Correct |
3 ms |
7376 KB |
Output is correct |
15 |
Correct |
3 ms |
7420 KB |
Output is correct |
16 |
Correct |
3 ms |
7380 KB |
Output is correct |
17 |
Correct |
3 ms |
7380 KB |
Output is correct |
18 |
Correct |
3 ms |
7380 KB |
Output is correct |
19 |
Correct |
3 ms |
7380 KB |
Output is correct |
20 |
Correct |
3 ms |
7380 KB |
Output is correct |
21 |
Correct |
3 ms |
7380 KB |
Output is correct |
22 |
Correct |
3 ms |
7380 KB |
Output is correct |
23 |
Correct |
3 ms |
7380 KB |
Output is correct |
24 |
Correct |
5 ms |
7380 KB |
Output is correct |
25 |
Correct |
3 ms |
7380 KB |
Output is correct |
26 |
Correct |
3 ms |
7380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7380 KB |
Output is correct |
2 |
Correct |
3 ms |
7332 KB |
Output is correct |
3 |
Correct |
3 ms |
7380 KB |
Output is correct |
4 |
Correct |
3 ms |
7380 KB |
Output is correct |
5 |
Correct |
3 ms |
7380 KB |
Output is correct |
6 |
Correct |
3 ms |
7380 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7380 KB |
Output is correct |
9 |
Correct |
3 ms |
7380 KB |
Output is correct |
10 |
Correct |
3 ms |
7380 KB |
Output is correct |
11 |
Correct |
3 ms |
7380 KB |
Output is correct |
12 |
Correct |
3 ms |
7380 KB |
Output is correct |
13 |
Correct |
3 ms |
7380 KB |
Output is correct |
14 |
Correct |
3 ms |
7376 KB |
Output is correct |
15 |
Correct |
3 ms |
7420 KB |
Output is correct |
16 |
Correct |
3 ms |
7380 KB |
Output is correct |
17 |
Correct |
3 ms |
7380 KB |
Output is correct |
18 |
Correct |
3 ms |
7380 KB |
Output is correct |
19 |
Correct |
3 ms |
7380 KB |
Output is correct |
20 |
Correct |
3 ms |
7380 KB |
Output is correct |
21 |
Correct |
3 ms |
7380 KB |
Output is correct |
22 |
Correct |
3 ms |
7380 KB |
Output is correct |
23 |
Correct |
3 ms |
7380 KB |
Output is correct |
24 |
Correct |
5 ms |
7380 KB |
Output is correct |
25 |
Correct |
3 ms |
7380 KB |
Output is correct |
26 |
Correct |
3 ms |
7380 KB |
Output is correct |
27 |
Correct |
4 ms |
7636 KB |
Output is correct |
28 |
Correct |
4 ms |
7592 KB |
Output is correct |
29 |
Correct |
4 ms |
7636 KB |
Output is correct |
30 |
Correct |
4 ms |
7508 KB |
Output is correct |
31 |
Correct |
4 ms |
7508 KB |
Output is correct |
32 |
Correct |
3 ms |
7380 KB |
Output is correct |
33 |
Correct |
4 ms |
7380 KB |
Output is correct |
34 |
Correct |
4 ms |
7636 KB |
Output is correct |
35 |
Correct |
4 ms |
7380 KB |
Output is correct |
36 |
Correct |
4 ms |
7508 KB |
Output is correct |
37 |
Correct |
5 ms |
7520 KB |
Output is correct |
38 |
Correct |
5 ms |
7636 KB |
Output is correct |
39 |
Correct |
6 ms |
7612 KB |
Output is correct |
40 |
Correct |
5 ms |
7472 KB |
Output is correct |
41 |
Correct |
4 ms |
7508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7380 KB |
Output is correct |
2 |
Correct |
3 ms |
7332 KB |
Output is correct |
3 |
Correct |
3 ms |
7380 KB |
Output is correct |
4 |
Correct |
3 ms |
7380 KB |
Output is correct |
5 |
Correct |
3 ms |
7380 KB |
Output is correct |
6 |
Correct |
3 ms |
7380 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7380 KB |
Output is correct |
9 |
Correct |
3 ms |
7380 KB |
Output is correct |
10 |
Correct |
113 ms |
32024 KB |
Output is correct |
11 |
Correct |
128 ms |
44912 KB |
Output is correct |
12 |
Correct |
25 ms |
13404 KB |
Output is correct |
13 |
Correct |
142 ms |
37568 KB |
Output is correct |
14 |
Correct |
144 ms |
84768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7380 KB |
Output is correct |
2 |
Correct |
3 ms |
7332 KB |
Output is correct |
3 |
Correct |
3 ms |
7380 KB |
Output is correct |
4 |
Correct |
3 ms |
7380 KB |
Output is correct |
5 |
Correct |
3 ms |
7380 KB |
Output is correct |
6 |
Correct |
3 ms |
7380 KB |
Output is correct |
7 |
Correct |
4 ms |
7380 KB |
Output is correct |
8 |
Correct |
4 ms |
7380 KB |
Output is correct |
9 |
Correct |
3 ms |
7380 KB |
Output is correct |
10 |
Correct |
3 ms |
7380 KB |
Output is correct |
11 |
Correct |
3 ms |
7380 KB |
Output is correct |
12 |
Correct |
3 ms |
7380 KB |
Output is correct |
13 |
Correct |
3 ms |
7380 KB |
Output is correct |
14 |
Correct |
3 ms |
7376 KB |
Output is correct |
15 |
Correct |
3 ms |
7420 KB |
Output is correct |
16 |
Correct |
3 ms |
7380 KB |
Output is correct |
17 |
Correct |
3 ms |
7380 KB |
Output is correct |
18 |
Correct |
3 ms |
7380 KB |
Output is correct |
19 |
Correct |
3 ms |
7380 KB |
Output is correct |
20 |
Correct |
3 ms |
7380 KB |
Output is correct |
21 |
Correct |
3 ms |
7380 KB |
Output is correct |
22 |
Correct |
3 ms |
7380 KB |
Output is correct |
23 |
Correct |
3 ms |
7380 KB |
Output is correct |
24 |
Correct |
5 ms |
7380 KB |
Output is correct |
25 |
Correct |
3 ms |
7380 KB |
Output is correct |
26 |
Correct |
3 ms |
7380 KB |
Output is correct |
27 |
Correct |
4 ms |
7636 KB |
Output is correct |
28 |
Correct |
4 ms |
7592 KB |
Output is correct |
29 |
Correct |
4 ms |
7636 KB |
Output is correct |
30 |
Correct |
4 ms |
7508 KB |
Output is correct |
31 |
Correct |
4 ms |
7508 KB |
Output is correct |
32 |
Correct |
3 ms |
7380 KB |
Output is correct |
33 |
Correct |
4 ms |
7380 KB |
Output is correct |
34 |
Correct |
4 ms |
7636 KB |
Output is correct |
35 |
Correct |
4 ms |
7380 KB |
Output is correct |
36 |
Correct |
4 ms |
7508 KB |
Output is correct |
37 |
Correct |
5 ms |
7520 KB |
Output is correct |
38 |
Correct |
5 ms |
7636 KB |
Output is correct |
39 |
Correct |
6 ms |
7612 KB |
Output is correct |
40 |
Correct |
5 ms |
7472 KB |
Output is correct |
41 |
Correct |
4 ms |
7508 KB |
Output is correct |
42 |
Correct |
113 ms |
32024 KB |
Output is correct |
43 |
Correct |
128 ms |
44912 KB |
Output is correct |
44 |
Correct |
25 ms |
13404 KB |
Output is correct |
45 |
Correct |
142 ms |
37568 KB |
Output is correct |
46 |
Correct |
144 ms |
84768 KB |
Output is correct |
47 |
Correct |
4 ms |
7380 KB |
Output is correct |
48 |
Correct |
3 ms |
7380 KB |
Output is correct |
49 |
Correct |
3 ms |
7380 KB |
Output is correct |
50 |
Correct |
109 ms |
63680 KB |
Output is correct |
51 |
Correct |
120 ms |
63644 KB |
Output is correct |
52 |
Correct |
121 ms |
34828 KB |
Output is correct |
53 |
Correct |
122 ms |
34884 KB |
Output is correct |
54 |
Correct |
131 ms |
34848 KB |
Output is correct |
55 |
Correct |
132 ms |
34080 KB |
Output is correct |
56 |
Correct |
185 ms |
42648 KB |
Output is correct |
57 |
Correct |
126 ms |
41392 KB |
Output is correct |
58 |
Correct |
193 ms |
50792 KB |
Output is correct |
59 |
Correct |
253 ms |
51516 KB |
Output is correct |
60 |
Correct |
159 ms |
39416 KB |
Output is correct |
61 |
Correct |
154 ms |
39444 KB |
Output is correct |
62 |
Correct |
132 ms |
36368 KB |
Output is correct |
63 |
Correct |
112 ms |
39628 KB |
Output is correct |
64 |
Correct |
5 ms |
8660 KB |
Output is correct |
65 |
Correct |
5 ms |
8660 KB |
Output is correct |
66 |
Correct |
174 ms |
36484 KB |
Output is correct |
67 |
Correct |
15 ms |
15104 KB |
Output is correct |
68 |
Correct |
23 ms |
20304 KB |
Output is correct |
69 |
Correct |
248 ms |
51472 KB |
Output is correct |
70 |
Correct |
43 ms |
33140 KB |
Output is correct |
71 |
Correct |
125 ms |
84760 KB |
Output is correct |
72 |
Correct |
232 ms |
51364 KB |
Output is correct |
73 |
Correct |
195 ms |
36596 KB |
Output is correct |