// podla https://codeforces.com/blog/entry/92083?#comment-807994
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <chrono>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <bitset>
#include <cmath>
#include <cassert>
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 3e5 + 5;
int par[maxn]; // aspon jeden z korenov tohto union-findu dava optimalnu odpoved.
int root(int u)
{
return par[u] == u ? u : par[u] = root(par[u]);
}
void merge(int p, int v)
{
par[root(v)] = root(p);
}
int ans = maxn; // minimalna dosiahnutelnost
vector<int> val; // hodnoty, ktore nadobudaju toto minimum
int mykey[maxn]; // moj kluc
vector<pair<int, int> > g[maxn]; // hrany
vector<int> locked[maxn]; // tie vrcholy, ku ktorym sa zatial neviem dostat
bool keys[maxn]; // keys[i] = mame kluc i?
int last[maxn]; // last[i] = posledna iteracia v ktorej sme navstivili ten vrchol i
bool out[maxn]; // out[i] = je i vrchol, z ktoreho sa uz nevieme dostat prec?
bool vis[maxn]; // vis[i] = navstiveny?
vector<int> reach; // kam sa vieme dostat?
void clear() // upraceme po bfsku
{
for (int i : reach)
{
keys[mykey[i]] = 0;
for (pair<int, int> j : g[i]) locked[j.second].clear();
}
reach.clear();
}
void find_better(int u, int round)
{
queue<int> q;
q.push(u);
while (q.size())
{
int v = q.front();
q.pop();
if (root(v) != u) // nasli sme vrchol, ktory je aspon taky dobry ako u
{
merge(v, u);
last[root(v)] = round;
clear();
return;
}
if (vis[v]) continue;
vis[v] = true;
reach.push_back(v);
if (!keys[mykey[v]]) // dostali sme novy kluc
{
keys[mykey[v]] = true;
for (int i : locked[mykey[v]]) q.push(i); // odomkli sa nam nove vrcholy
locked[mykey[v]].clear();
}
for (pair<int, int> i : g[v]) // ideme popozerat hrany odtialto a rozsirit sa
{
if (keys[i.second]) q.push(i.first); // mame spravny kluc
else locked[i.second].push_back(i.first); // nemame spravny kluc
}
}
out[u] = true; // nevieme uz nikde inde ist, takze u je jeden z kandidatov na odpoved
if (reach.size() < ans) ans = reach.size(), val.clear();
if (reach.size() == ans) for (int i : reach) val.push_back(i);
clear();
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
int n = r.size(), m = u.size();
for (int i = 0; i < n; i++) mykey[i] = r[i], par[i] = i;
for (int i = 0; i < m; i++) g[u[i]].push_back({ v[i],c[i] }), g[v[i]].push_back({ u[i], c[i] });
for (int round = 1; ; round++)
{
fill(vis, vis + maxn, false);
bool change = false;
for (int i = 0; i < n; i++) if (i == par[i] && !out[i] && last[i] != round)
find_better(i, round), change = true;
if (!change) break;
}
vector<int> ans(n, 0);
for (int i : val) ans[i] = 1;
return ans;
}
Compilation message
keys.cpp: In function 'void find_better(int, int)':
keys.cpp:80:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if (reach.size() < ans) ans = reach.size(), val.clear();
| ~~~~~~~~~~~~~^~~~~
keys.cpp:81:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
81 | if (reach.size() == ans) for (int i : reach) val.push_back(i);
| ~~~~~~~~~~~~~^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14668 KB |
Output is correct |
2 |
Correct |
7 ms |
14668 KB |
Output is correct |
3 |
Correct |
7 ms |
14668 KB |
Output is correct |
4 |
Correct |
7 ms |
14668 KB |
Output is correct |
5 |
Correct |
7 ms |
14668 KB |
Output is correct |
6 |
Correct |
7 ms |
14644 KB |
Output is correct |
7 |
Correct |
8 ms |
14624 KB |
Output is correct |
8 |
Correct |
8 ms |
14668 KB |
Output is correct |
9 |
Correct |
8 ms |
14632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14668 KB |
Output is correct |
2 |
Correct |
7 ms |
14668 KB |
Output is correct |
3 |
Correct |
7 ms |
14668 KB |
Output is correct |
4 |
Correct |
7 ms |
14668 KB |
Output is correct |
5 |
Correct |
7 ms |
14668 KB |
Output is correct |
6 |
Correct |
7 ms |
14644 KB |
Output is correct |
7 |
Correct |
8 ms |
14624 KB |
Output is correct |
8 |
Correct |
8 ms |
14668 KB |
Output is correct |
9 |
Correct |
8 ms |
14632 KB |
Output is correct |
10 |
Correct |
9 ms |
14636 KB |
Output is correct |
11 |
Correct |
8 ms |
14668 KB |
Output is correct |
12 |
Correct |
8 ms |
14728 KB |
Output is correct |
13 |
Correct |
9 ms |
14668 KB |
Output is correct |
14 |
Correct |
8 ms |
14668 KB |
Output is correct |
15 |
Correct |
8 ms |
14668 KB |
Output is correct |
16 |
Correct |
8 ms |
14672 KB |
Output is correct |
17 |
Correct |
8 ms |
14652 KB |
Output is correct |
18 |
Correct |
8 ms |
14668 KB |
Output is correct |
19 |
Correct |
8 ms |
14592 KB |
Output is correct |
20 |
Correct |
8 ms |
14668 KB |
Output is correct |
21 |
Correct |
8 ms |
14668 KB |
Output is correct |
22 |
Correct |
8 ms |
14668 KB |
Output is correct |
23 |
Correct |
8 ms |
14632 KB |
Output is correct |
24 |
Correct |
8 ms |
14688 KB |
Output is correct |
25 |
Correct |
8 ms |
14644 KB |
Output is correct |
26 |
Correct |
8 ms |
14668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14668 KB |
Output is correct |
2 |
Correct |
7 ms |
14668 KB |
Output is correct |
3 |
Correct |
7 ms |
14668 KB |
Output is correct |
4 |
Correct |
7 ms |
14668 KB |
Output is correct |
5 |
Correct |
7 ms |
14668 KB |
Output is correct |
6 |
Correct |
7 ms |
14644 KB |
Output is correct |
7 |
Correct |
8 ms |
14624 KB |
Output is correct |
8 |
Correct |
8 ms |
14668 KB |
Output is correct |
9 |
Correct |
8 ms |
14632 KB |
Output is correct |
10 |
Correct |
9 ms |
14636 KB |
Output is correct |
11 |
Correct |
8 ms |
14668 KB |
Output is correct |
12 |
Correct |
8 ms |
14728 KB |
Output is correct |
13 |
Correct |
9 ms |
14668 KB |
Output is correct |
14 |
Correct |
8 ms |
14668 KB |
Output is correct |
15 |
Correct |
8 ms |
14668 KB |
Output is correct |
16 |
Correct |
8 ms |
14672 KB |
Output is correct |
17 |
Correct |
8 ms |
14652 KB |
Output is correct |
18 |
Correct |
8 ms |
14668 KB |
Output is correct |
19 |
Correct |
8 ms |
14592 KB |
Output is correct |
20 |
Correct |
8 ms |
14668 KB |
Output is correct |
21 |
Correct |
8 ms |
14668 KB |
Output is correct |
22 |
Correct |
8 ms |
14668 KB |
Output is correct |
23 |
Correct |
8 ms |
14632 KB |
Output is correct |
24 |
Correct |
8 ms |
14688 KB |
Output is correct |
25 |
Correct |
8 ms |
14644 KB |
Output is correct |
26 |
Correct |
8 ms |
14668 KB |
Output is correct |
27 |
Correct |
9 ms |
14944 KB |
Output is correct |
28 |
Correct |
11 ms |
14924 KB |
Output is correct |
29 |
Correct |
9 ms |
14908 KB |
Output is correct |
30 |
Correct |
11 ms |
14764 KB |
Output is correct |
31 |
Correct |
9 ms |
14804 KB |
Output is correct |
32 |
Correct |
8 ms |
14668 KB |
Output is correct |
33 |
Correct |
8 ms |
14672 KB |
Output is correct |
34 |
Correct |
9 ms |
14820 KB |
Output is correct |
35 |
Correct |
8 ms |
14800 KB |
Output is correct |
36 |
Correct |
9 ms |
14836 KB |
Output is correct |
37 |
Correct |
10 ms |
14924 KB |
Output is correct |
38 |
Correct |
10 ms |
14928 KB |
Output is correct |
39 |
Correct |
9 ms |
14920 KB |
Output is correct |
40 |
Correct |
9 ms |
14796 KB |
Output is correct |
41 |
Correct |
12 ms |
14796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14668 KB |
Output is correct |
2 |
Correct |
7 ms |
14668 KB |
Output is correct |
3 |
Correct |
7 ms |
14668 KB |
Output is correct |
4 |
Correct |
7 ms |
14668 KB |
Output is correct |
5 |
Correct |
7 ms |
14668 KB |
Output is correct |
6 |
Correct |
7 ms |
14644 KB |
Output is correct |
7 |
Correct |
8 ms |
14624 KB |
Output is correct |
8 |
Correct |
8 ms |
14668 KB |
Output is correct |
9 |
Correct |
8 ms |
14632 KB |
Output is correct |
10 |
Correct |
198 ms |
39152 KB |
Output is correct |
11 |
Correct |
255 ms |
48460 KB |
Output is correct |
12 |
Correct |
54 ms |
20684 KB |
Output is correct |
13 |
Correct |
249 ms |
43316 KB |
Output is correct |
14 |
Correct |
175 ms |
45620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14668 KB |
Output is correct |
2 |
Correct |
7 ms |
14668 KB |
Output is correct |
3 |
Correct |
7 ms |
14668 KB |
Output is correct |
4 |
Correct |
7 ms |
14668 KB |
Output is correct |
5 |
Correct |
7 ms |
14668 KB |
Output is correct |
6 |
Correct |
7 ms |
14644 KB |
Output is correct |
7 |
Correct |
8 ms |
14624 KB |
Output is correct |
8 |
Correct |
8 ms |
14668 KB |
Output is correct |
9 |
Correct |
8 ms |
14632 KB |
Output is correct |
10 |
Correct |
9 ms |
14636 KB |
Output is correct |
11 |
Correct |
8 ms |
14668 KB |
Output is correct |
12 |
Correct |
8 ms |
14728 KB |
Output is correct |
13 |
Correct |
9 ms |
14668 KB |
Output is correct |
14 |
Correct |
8 ms |
14668 KB |
Output is correct |
15 |
Correct |
8 ms |
14668 KB |
Output is correct |
16 |
Correct |
8 ms |
14672 KB |
Output is correct |
17 |
Correct |
8 ms |
14652 KB |
Output is correct |
18 |
Correct |
8 ms |
14668 KB |
Output is correct |
19 |
Correct |
8 ms |
14592 KB |
Output is correct |
20 |
Correct |
8 ms |
14668 KB |
Output is correct |
21 |
Correct |
8 ms |
14668 KB |
Output is correct |
22 |
Correct |
8 ms |
14668 KB |
Output is correct |
23 |
Correct |
8 ms |
14632 KB |
Output is correct |
24 |
Correct |
8 ms |
14688 KB |
Output is correct |
25 |
Correct |
8 ms |
14644 KB |
Output is correct |
26 |
Correct |
8 ms |
14668 KB |
Output is correct |
27 |
Correct |
9 ms |
14944 KB |
Output is correct |
28 |
Correct |
11 ms |
14924 KB |
Output is correct |
29 |
Correct |
9 ms |
14908 KB |
Output is correct |
30 |
Correct |
11 ms |
14764 KB |
Output is correct |
31 |
Correct |
9 ms |
14804 KB |
Output is correct |
32 |
Correct |
8 ms |
14668 KB |
Output is correct |
33 |
Correct |
8 ms |
14672 KB |
Output is correct |
34 |
Correct |
9 ms |
14820 KB |
Output is correct |
35 |
Correct |
8 ms |
14800 KB |
Output is correct |
36 |
Correct |
9 ms |
14836 KB |
Output is correct |
37 |
Correct |
10 ms |
14924 KB |
Output is correct |
38 |
Correct |
10 ms |
14928 KB |
Output is correct |
39 |
Correct |
9 ms |
14920 KB |
Output is correct |
40 |
Correct |
9 ms |
14796 KB |
Output is correct |
41 |
Correct |
12 ms |
14796 KB |
Output is correct |
42 |
Correct |
198 ms |
39152 KB |
Output is correct |
43 |
Correct |
255 ms |
48460 KB |
Output is correct |
44 |
Correct |
54 ms |
20684 KB |
Output is correct |
45 |
Correct |
249 ms |
43316 KB |
Output is correct |
46 |
Correct |
175 ms |
45620 KB |
Output is correct |
47 |
Correct |
7 ms |
14668 KB |
Output is correct |
48 |
Correct |
7 ms |
14668 KB |
Output is correct |
49 |
Correct |
7 ms |
14656 KB |
Output is correct |
50 |
Correct |
164 ms |
45872 KB |
Output is correct |
51 |
Correct |
207 ms |
47412 KB |
Output is correct |
52 |
Correct |
238 ms |
44220 KB |
Output is correct |
53 |
Correct |
236 ms |
44012 KB |
Output is correct |
54 |
Correct |
231 ms |
44096 KB |
Output is correct |
55 |
Correct |
279 ms |
41328 KB |
Output is correct |
56 |
Correct |
332 ms |
52984 KB |
Output is correct |
57 |
Correct |
274 ms |
49896 KB |
Output is correct |
58 |
Correct |
291 ms |
56796 KB |
Output is correct |
59 |
Correct |
442 ms |
51092 KB |
Output is correct |
60 |
Correct |
301 ms |
48580 KB |
Output is correct |
61 |
Correct |
359 ms |
50648 KB |
Output is correct |
62 |
Correct |
743 ms |
45968 KB |
Output is correct |
63 |
Correct |
167 ms |
46176 KB |
Output is correct |
64 |
Correct |
12 ms |
15184 KB |
Output is correct |
65 |
Correct |
10 ms |
15180 KB |
Output is correct |
66 |
Correct |
692 ms |
45880 KB |
Output is correct |
67 |
Correct |
24 ms |
17860 KB |
Output is correct |
68 |
Correct |
37 ms |
20036 KB |
Output is correct |
69 |
Correct |
424 ms |
51216 KB |
Output is correct |
70 |
Correct |
59 ms |
25316 KB |
Output is correct |
71 |
Correct |
204 ms |
47216 KB |
Output is correct |
72 |
Correct |
387 ms |
51004 KB |
Output is correct |
73 |
Correct |
658 ms |
45876 KB |
Output is correct |