/*
author: Maksim1744
created: 04.12.2021 11:30:50
*/
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;}
template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun) fun
#define debugv(var) var
#define mclock void(0)
#define shows void(0)
#define debug if (false)
#endif
template<class Fun>
class y_combinator_result {
Fun fun_;
public:
template<class T>
explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
// auto gcd = std::y_combinator([](auto gcd, int a, int b) -> int {
// return b == 0 ? a : gcd(b, a % b);
// });
vector<int> scc(vector<vector<int>>& g, vector<vector<int>>& gi) {
int n = g.size();
vector<int> topsort; topsort.reserve(n);
vector<bool> u(n, false);
auto scc_dfs1 = y_combinator([&](auto scc_dfs1, int v) -> void {
u[v] = true;
for (auto k : g[v])
if (!u[k])
scc_dfs1(k);
topsort.push_back(v);
});
for (int i = 0; i < n; ++i)
if (!u[i])
scc_dfs1(i);
int color = 0;
vector<int> comp(n, -1);
reverse(topsort.begin(), topsort.end());
auto scc_dfs2 = y_combinator([&](auto scc_dfs2, int v, int color) -> void {
comp[v] = color;
for (auto k : gi[v])
if (comp[k] == -1)
scc_dfs2(k, color);
});
for (auto v : topsort)
if (comp[v] == -1)
scc_dfs2(v, color++);
return comp;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
vector<vector<pair<int, pair<int, int>>>> g(n);
for (int i = 0; i < u.size(); ++i) {
g[u[i]].eb(v[i], mp(i * 2 + 0, c[i]));
g[v[i]].eb(u[i], mp(i * 2 + 1, c[i]));
}
vector<vector<int>> go(n);
vector<vector<int>> goi(n);
vector<bool> ue(u.size() * 2, false);
bool because_change = false;
vector<int> cur(n, 0);
int icur = 0;
for (int iter = 0; iter < 1e2/2; ++iter) {
bool change = false;
auto col = scc(go, goi);
vector<vector<int>> comps(maxe(col) + 1);
for (int i = 0; i < n; ++i) {
comps[col[i]].pb(i);
}
for (int i = 0; i < comps.size(); ++i) {
++icur;
for (int v : comps[i]) {
cur[r[v]] = icur;
}
for (int v : comps[i]) {
for (auto [u, ic] : g[v]) {
auto [ind, c] = ic;
if (col[u] == col[v]) continue;
if (cur[c] != icur) continue;
if (ue[ind]) continue;
ue[ind] = true;
go[v].pb(u);
goi[u].pb(v);
change = true;
}
}
}
show(go, change);
if (!change) {
because_change = true;
break;
}
}
auto col = scc(go, goi);
vector<bool> terminal(maxe(col) + 1, true);
for (int i = 0; i < n; ++i) {
for (auto j : go[i]) {
if (col[i] == col[j]) continue;
terminal[col[i]] = false;
}
}
show(go);
show(col);
show(terminal);
vector<int> sz(terminal.size(), 1e9);
vector<pair<int, vector<int>>> tos(n, {-1, {}});
vector<int> has(n, -1);
int ihas = 0;
vector<bool> uu(n, false);
auto reachable = [&](int v) {
++ihas;
queue<int> q;
int ans = 0;
q.push(v);
uu.assign(n, false);
while (!q.empty()) {
auto v = q.front();
q.pop();
if (uu[v]) continue;
uu[v] = true;
++ans;
if (has[r[v]] != ihas) {
has[r[v]] = ihas;
if (tos[r[v]].first != ihas) tos[r[v]].second.clear();
for (int k : tos[r[v]].second)
q.push(k);
}
for (auto [k, ic] : g[v]) {
auto [ind, c] = ic;
if (has[c] == ihas)
q.push(k);
else {
if (tos[c].first != ihas) {
tos[c].first = ihas;
tos[c].second.clear();
}
tos[c].second.pb(k);
}
}
}
show(v, ans);
return ans;
};
if (because_change) {
for (int i = 0; i < n; ++i) {
if (terminal[col[i]])
sz[col[i]] = 0;
}
for (int i = 0; i < n; ++i) {
sz[col[i]]++;
}
} else {
vector<int> check;
for (int i = 0; i < n; ++i) {
if (terminal[col[i]]) {
terminal[col[i]] = false;
check.pb(i);
}
}
for (int v : check) {
sz[col[v]] = reachable(v);
}
}
show(sz);
vector<int> ans(n, 0);
int mnsz = mine(sz);
for (int i = 0; i < n; ++i) {
if (sz[col[i]] == mnsz) {
ans[i] = 1;
}
}
return ans;
}
#ifdef HOUSE
int main() {
int n, m;
assert(2 == scanf("%d%d", &n, &m));
std::vector<int> r(n), u(m), v(m), c(m);
for(int i=0; i<n; i++) {
assert(1 == scanf("%d", &r[i]));
}
for(int i=0; i<m; i++) {
assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
}
fclose(stdin);
std::vector<int> ans = find_reachable(r, u, v, c);
for (int i = 0; i < (int) ans.size(); ++i) {
if(i) putchar(' ');
putchar(ans[i]+'0');
}
printf("\n");
return 0;
}
#endif
Compilation message
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int i = 0; i < u.size(); ++i) {
| ~~^~~~~~~~~~
keys.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for (int i = 0; i < comps.size(); ++i) {
| ~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
716 KB |
Output is correct |
28 |
Correct |
2 ms |
716 KB |
Output is correct |
29 |
Correct |
2 ms |
716 KB |
Output is correct |
30 |
Correct |
1 ms |
460 KB |
Output is correct |
31 |
Correct |
1 ms |
460 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
460 KB |
Output is correct |
34 |
Correct |
1 ms |
460 KB |
Output is correct |
35 |
Correct |
1 ms |
460 KB |
Output is correct |
36 |
Correct |
2 ms |
716 KB |
Output is correct |
37 |
Correct |
2 ms |
716 KB |
Output is correct |
38 |
Correct |
2 ms |
716 KB |
Output is correct |
39 |
Correct |
2 ms |
716 KB |
Output is correct |
40 |
Correct |
1 ms |
460 KB |
Output is correct |
41 |
Correct |
2 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
2407 ms |
41776 KB |
Output is correct |
11 |
Correct |
416 ms |
93620 KB |
Output is correct |
12 |
Correct |
88 ms |
15112 KB |
Output is correct |
13 |
Correct |
655 ms |
78220 KB |
Output is correct |
14 |
Correct |
250 ms |
93736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
716 KB |
Output is correct |
28 |
Correct |
2 ms |
716 KB |
Output is correct |
29 |
Correct |
2 ms |
716 KB |
Output is correct |
30 |
Correct |
1 ms |
460 KB |
Output is correct |
31 |
Correct |
1 ms |
460 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
460 KB |
Output is correct |
34 |
Correct |
1 ms |
460 KB |
Output is correct |
35 |
Correct |
1 ms |
460 KB |
Output is correct |
36 |
Correct |
2 ms |
716 KB |
Output is correct |
37 |
Correct |
2 ms |
716 KB |
Output is correct |
38 |
Correct |
2 ms |
716 KB |
Output is correct |
39 |
Correct |
2 ms |
716 KB |
Output is correct |
40 |
Correct |
1 ms |
460 KB |
Output is correct |
41 |
Correct |
2 ms |
588 KB |
Output is correct |
42 |
Correct |
2407 ms |
41776 KB |
Output is correct |
43 |
Correct |
416 ms |
93620 KB |
Output is correct |
44 |
Correct |
88 ms |
15112 KB |
Output is correct |
45 |
Correct |
655 ms |
78220 KB |
Output is correct |
46 |
Correct |
250 ms |
93736 KB |
Output is correct |
47 |
Correct |
0 ms |
204 KB |
Output is correct |
48 |
Correct |
1 ms |
204 KB |
Output is correct |
49 |
Correct |
0 ms |
204 KB |
Output is correct |
50 |
Correct |
232 ms |
92172 KB |
Output is correct |
51 |
Correct |
257 ms |
91380 KB |
Output is correct |
52 |
Correct |
336 ms |
61000 KB |
Output is correct |
53 |
Correct |
321 ms |
60980 KB |
Output is correct |
54 |
Correct |
339 ms |
60892 KB |
Output is correct |
55 |
Correct |
2267 ms |
47132 KB |
Output is correct |
56 |
Correct |
553 ms |
93032 KB |
Output is correct |
57 |
Correct |
354 ms |
78952 KB |
Output is correct |
58 |
Correct |
343 ms |
79084 KB |
Output is correct |
59 |
Correct |
439 ms |
68584 KB |
Output is correct |
60 |
Correct |
486 ms |
73516 KB |
Output is correct |
61 |
Correct |
503 ms |
73872 KB |
Output is correct |
62 |
Correct |
1272 ms |
56204 KB |
Output is correct |
63 |
Correct |
219 ms |
58560 KB |
Output is correct |
64 |
Correct |
4 ms |
1740 KB |
Output is correct |
65 |
Correct |
4 ms |
1824 KB |
Output is correct |
66 |
Correct |
1300 ms |
55332 KB |
Output is correct |
67 |
Correct |
24 ms |
9740 KB |
Output is correct |
68 |
Correct |
41 ms |
15848 KB |
Output is correct |
69 |
Correct |
455 ms |
67908 KB |
Output is correct |
70 |
Correct |
85 ms |
31456 KB |
Output is correct |
71 |
Correct |
270 ms |
94444 KB |
Output is correct |
72 |
Correct |
415 ms |
68668 KB |
Output is correct |
73 |
Correct |
1248 ms |
56072 KB |
Output is correct |