# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
820872 |
2023-08-11T06:22:30 Z |
LittleCube |
Keys (IOI21_keys) |
C++17 |
|
1200 ms |
139228 KB |
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int n, m, k, out[300000], vis[300000], res[300000];
set<int> keys[300000];
vector<int> edge[600000], reach[300000];
map<int, int> mp[300000];
struct dsu
{
int dsu[300000], rk[300000];
void init()
{
for (int i = 0; i < n; i++)
dsu[i] = i, rk[i] = 1;
}
int find(int k)
{
return dsu[k] == k ? k : dsu[k] = find(dsu[k]);
}
} ptree, scc;
void merge(vector<int> &a, vector<int> &b)
{
if (a.size() < b.size())
swap(a, b);
for (auto i : b)
a.emplace_back(i);
b.clear();
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
n = r.size();
m = u.size();
ptree.init(), scc.init();
for (int i = 0; i < n; i++)
keys[i].insert(r[i]);
for (int i = 0; i < m; i++)
{
if (mp[u[i]][c[i]] == 0)
mp[u[i]][c[i]] = ++k;
if (mp[v[i]][c[i]] == 0)
mp[v[i]][c[i]] = ++k;
edge[mp[u[i]][c[i]]].emplace_back(v[i]);
edge[mp[v[i]][c[i]]].emplace_back(u[i]);
}
for (int i = 0; i < n; i++)
out[i] = i, res[i] = n + 1;
for (int i = 0; i < n; i++)
if (mp[i].find(r[i]) != mp[i].end())
{
auto iter = mp[i].find(r[i]);
int p = iter->second;
mp[i].erase(iter);
merge(reach[i], edge[p]);
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 0; i < n; i++)
pq.push(pii(1, i));
int last = n + 1;
while (!pq.empty())
{
auto [s, u] = pq.top();
// u should be the root of pseudo-trees and the representative of its scc
pq.pop();
if (s > last)
break;
while (!reach[u].empty() && scc.find(reach[u].back()) == u)
reach[u].pop_back();
if (reach[u].empty())
{
// not augumentable, check until all scc > s
res[u] = s;
last = s;
continue;
}
int v = scc.find(reach[u].back());
if (ptree.find(v) != u)
{
out[u] = v, ptree.dsu[u] = ptree.find(v);
continue;
}
// augument
while (v != u)
{
int nxt = scc.find(out[v]);
// if (keys[v].size() > keys[u].size())
// {
// swap(out[u], out[v]);
// swap(u, v);
// }
merge(reach[u], reach[v]);
for (auto i : keys[v])
if (keys[u].find(i) == keys[u].end())
{
keys[u].insert(i);
auto iter = mp[u].find(i);
if (iter != mp[u].end())
{
int p = iter->second;
mp[u].erase(iter);
merge(reach[u], edge[p]);
}
}
for (auto [c, p] : mp[v])
{
if (keys[u].find(c) != keys[u].end())
merge(reach[u], edge[p]);
else
{
int q = mp[u][c];
if (q == 0)
mp[u][c] = p;
else
merge(edge[q], edge[p]);
}
}
ptree.dsu[v] = u;
scc.dsu[v] = u;
scc.rk[u] += scc.rk[v];
v = nxt;
}
pq.push(pii(scc.rk[u], u));
}
for (int i = 0; i < n; i++)
res[i] = res[scc.find(i)];
last = *min_element(res, res + n);
vector<int> ans(n);
for (int i = 0; i < n; i++)
ans[i] = res[i] == last;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
49644 KB |
Output is correct |
2 |
Correct |
21 ms |
49580 KB |
Output is correct |
3 |
Correct |
21 ms |
49648 KB |
Output is correct |
4 |
Correct |
22 ms |
49628 KB |
Output is correct |
5 |
Correct |
24 ms |
49656 KB |
Output is correct |
6 |
Correct |
22 ms |
49624 KB |
Output is correct |
7 |
Correct |
23 ms |
49628 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
22 ms |
49580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
49644 KB |
Output is correct |
2 |
Correct |
21 ms |
49580 KB |
Output is correct |
3 |
Correct |
21 ms |
49648 KB |
Output is correct |
4 |
Correct |
22 ms |
49628 KB |
Output is correct |
5 |
Correct |
24 ms |
49656 KB |
Output is correct |
6 |
Correct |
22 ms |
49624 KB |
Output is correct |
7 |
Correct |
23 ms |
49628 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
22 ms |
49580 KB |
Output is correct |
10 |
Correct |
22 ms |
49684 KB |
Output is correct |
11 |
Correct |
22 ms |
49628 KB |
Output is correct |
12 |
Correct |
23 ms |
49620 KB |
Output is correct |
13 |
Correct |
22 ms |
49540 KB |
Output is correct |
14 |
Correct |
23 ms |
49536 KB |
Output is correct |
15 |
Correct |
22 ms |
49620 KB |
Output is correct |
16 |
Correct |
21 ms |
49588 KB |
Output is correct |
17 |
Correct |
24 ms |
49620 KB |
Output is correct |
18 |
Correct |
22 ms |
49632 KB |
Output is correct |
19 |
Correct |
21 ms |
49628 KB |
Output is correct |
20 |
Correct |
23 ms |
49640 KB |
Output is correct |
21 |
Correct |
21 ms |
49628 KB |
Output is correct |
22 |
Correct |
22 ms |
49540 KB |
Output is correct |
23 |
Correct |
21 ms |
49672 KB |
Output is correct |
24 |
Correct |
23 ms |
49604 KB |
Output is correct |
25 |
Correct |
23 ms |
49628 KB |
Output is correct |
26 |
Correct |
22 ms |
49628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
49644 KB |
Output is correct |
2 |
Correct |
21 ms |
49580 KB |
Output is correct |
3 |
Correct |
21 ms |
49648 KB |
Output is correct |
4 |
Correct |
22 ms |
49628 KB |
Output is correct |
5 |
Correct |
24 ms |
49656 KB |
Output is correct |
6 |
Correct |
22 ms |
49624 KB |
Output is correct |
7 |
Correct |
23 ms |
49628 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
22 ms |
49580 KB |
Output is correct |
10 |
Correct |
22 ms |
49684 KB |
Output is correct |
11 |
Correct |
22 ms |
49628 KB |
Output is correct |
12 |
Correct |
23 ms |
49620 KB |
Output is correct |
13 |
Correct |
22 ms |
49540 KB |
Output is correct |
14 |
Correct |
23 ms |
49536 KB |
Output is correct |
15 |
Correct |
22 ms |
49620 KB |
Output is correct |
16 |
Correct |
21 ms |
49588 KB |
Output is correct |
17 |
Correct |
24 ms |
49620 KB |
Output is correct |
18 |
Correct |
22 ms |
49632 KB |
Output is correct |
19 |
Correct |
21 ms |
49628 KB |
Output is correct |
20 |
Correct |
23 ms |
49640 KB |
Output is correct |
21 |
Correct |
21 ms |
49628 KB |
Output is correct |
22 |
Correct |
22 ms |
49540 KB |
Output is correct |
23 |
Correct |
21 ms |
49672 KB |
Output is correct |
24 |
Correct |
23 ms |
49604 KB |
Output is correct |
25 |
Correct |
23 ms |
49628 KB |
Output is correct |
26 |
Correct |
22 ms |
49628 KB |
Output is correct |
27 |
Correct |
23 ms |
50152 KB |
Output is correct |
28 |
Correct |
24 ms |
50208 KB |
Output is correct |
29 |
Correct |
28 ms |
50156 KB |
Output is correct |
30 |
Correct |
23 ms |
50004 KB |
Output is correct |
31 |
Correct |
22 ms |
49748 KB |
Output is correct |
32 |
Correct |
21 ms |
49632 KB |
Output is correct |
33 |
Correct |
22 ms |
49812 KB |
Output is correct |
34 |
Correct |
22 ms |
49884 KB |
Output is correct |
35 |
Correct |
23 ms |
49872 KB |
Output is correct |
36 |
Correct |
24 ms |
50152 KB |
Output is correct |
37 |
Correct |
23 ms |
50132 KB |
Output is correct |
38 |
Correct |
23 ms |
50228 KB |
Output is correct |
39 |
Correct |
23 ms |
50200 KB |
Output is correct |
40 |
Correct |
23 ms |
49904 KB |
Output is correct |
41 |
Correct |
26 ms |
50024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
49644 KB |
Output is correct |
2 |
Correct |
21 ms |
49580 KB |
Output is correct |
3 |
Correct |
21 ms |
49648 KB |
Output is correct |
4 |
Correct |
22 ms |
49628 KB |
Output is correct |
5 |
Correct |
24 ms |
49656 KB |
Output is correct |
6 |
Correct |
22 ms |
49624 KB |
Output is correct |
7 |
Correct |
23 ms |
49628 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
22 ms |
49580 KB |
Output is correct |
10 |
Correct |
464 ms |
107396 KB |
Output is correct |
11 |
Correct |
462 ms |
113340 KB |
Output is correct |
12 |
Correct |
114 ms |
65732 KB |
Output is correct |
13 |
Correct |
604 ms |
129632 KB |
Output is correct |
14 |
Correct |
223 ms |
122252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
49644 KB |
Output is correct |
2 |
Correct |
21 ms |
49580 KB |
Output is correct |
3 |
Correct |
21 ms |
49648 KB |
Output is correct |
4 |
Correct |
22 ms |
49628 KB |
Output is correct |
5 |
Correct |
24 ms |
49656 KB |
Output is correct |
6 |
Correct |
22 ms |
49624 KB |
Output is correct |
7 |
Correct |
23 ms |
49628 KB |
Output is correct |
8 |
Correct |
21 ms |
49620 KB |
Output is correct |
9 |
Correct |
22 ms |
49580 KB |
Output is correct |
10 |
Correct |
22 ms |
49684 KB |
Output is correct |
11 |
Correct |
22 ms |
49628 KB |
Output is correct |
12 |
Correct |
23 ms |
49620 KB |
Output is correct |
13 |
Correct |
22 ms |
49540 KB |
Output is correct |
14 |
Correct |
23 ms |
49536 KB |
Output is correct |
15 |
Correct |
22 ms |
49620 KB |
Output is correct |
16 |
Correct |
21 ms |
49588 KB |
Output is correct |
17 |
Correct |
24 ms |
49620 KB |
Output is correct |
18 |
Correct |
22 ms |
49632 KB |
Output is correct |
19 |
Correct |
21 ms |
49628 KB |
Output is correct |
20 |
Correct |
23 ms |
49640 KB |
Output is correct |
21 |
Correct |
21 ms |
49628 KB |
Output is correct |
22 |
Correct |
22 ms |
49540 KB |
Output is correct |
23 |
Correct |
21 ms |
49672 KB |
Output is correct |
24 |
Correct |
23 ms |
49604 KB |
Output is correct |
25 |
Correct |
23 ms |
49628 KB |
Output is correct |
26 |
Correct |
22 ms |
49628 KB |
Output is correct |
27 |
Correct |
23 ms |
50152 KB |
Output is correct |
28 |
Correct |
24 ms |
50208 KB |
Output is correct |
29 |
Correct |
28 ms |
50156 KB |
Output is correct |
30 |
Correct |
23 ms |
50004 KB |
Output is correct |
31 |
Correct |
22 ms |
49748 KB |
Output is correct |
32 |
Correct |
21 ms |
49632 KB |
Output is correct |
33 |
Correct |
22 ms |
49812 KB |
Output is correct |
34 |
Correct |
22 ms |
49884 KB |
Output is correct |
35 |
Correct |
23 ms |
49872 KB |
Output is correct |
36 |
Correct |
24 ms |
50152 KB |
Output is correct |
37 |
Correct |
23 ms |
50132 KB |
Output is correct |
38 |
Correct |
23 ms |
50228 KB |
Output is correct |
39 |
Correct |
23 ms |
50200 KB |
Output is correct |
40 |
Correct |
23 ms |
49904 KB |
Output is correct |
41 |
Correct |
26 ms |
50024 KB |
Output is correct |
42 |
Correct |
464 ms |
107396 KB |
Output is correct |
43 |
Correct |
462 ms |
113340 KB |
Output is correct |
44 |
Correct |
114 ms |
65732 KB |
Output is correct |
45 |
Correct |
604 ms |
129632 KB |
Output is correct |
46 |
Correct |
223 ms |
122252 KB |
Output is correct |
47 |
Correct |
23 ms |
49536 KB |
Output is correct |
48 |
Correct |
24 ms |
49620 KB |
Output is correct |
49 |
Correct |
23 ms |
49628 KB |
Output is correct |
50 |
Correct |
201 ms |
112808 KB |
Output is correct |
51 |
Correct |
202 ms |
115736 KB |
Output is correct |
52 |
Correct |
327 ms |
108680 KB |
Output is correct |
53 |
Correct |
328 ms |
108812 KB |
Output is correct |
54 |
Correct |
314 ms |
108684 KB |
Output is correct |
55 |
Correct |
423 ms |
113864 KB |
Output is correct |
56 |
Correct |
367 ms |
125232 KB |
Output is correct |
57 |
Correct |
235 ms |
117016 KB |
Output is correct |
58 |
Correct |
683 ms |
139228 KB |
Output is correct |
59 |
Correct |
1200 ms |
130808 KB |
Output is correct |
60 |
Correct |
480 ms |
122596 KB |
Output is correct |
61 |
Correct |
915 ms |
126944 KB |
Output is correct |
62 |
Correct |
624 ms |
115724 KB |
Output is correct |
63 |
Correct |
355 ms |
125368 KB |
Output is correct |
64 |
Correct |
26 ms |
50772 KB |
Output is correct |
65 |
Correct |
25 ms |
50772 KB |
Output is correct |
66 |
Correct |
604 ms |
115868 KB |
Output is correct |
67 |
Correct |
40 ms |
56672 KB |
Output is correct |
68 |
Correct |
58 ms |
61408 KB |
Output is correct |
69 |
Correct |
1068 ms |
130964 KB |
Output is correct |
70 |
Correct |
80 ms |
73416 KB |
Output is correct |
71 |
Correct |
214 ms |
122844 KB |
Output is correct |
72 |
Correct |
1113 ms |
130860 KB |
Output is correct |
73 |
Correct |
647 ms |
115736 KB |
Output is correct |