#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 600005;
struct disj{
int pa[MAXN];
void init(){
iota(pa, pa + MAXN, 0);
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;
set<int> keys[MAXN];
set<pi> gph[MAXN];
vector<int> canReach[MAXN];
int comp[MAXN], nxt[MAXN];
int idx[MAXN], sz[MAXN];
int find(int x){
return comp[x] = (comp[x] == x ? x : find(comp[x]));
}
int cnt = 0;
void merge_to(int u, int v){
u = find(u);
cnt++;
if(cnt >= 2000000) assert(0);
if(u == v) return;
comp[u] = v;
int iu = idx[u], iv = idx[v];
if(sz[u] > sz[v]) swap(iu, iv);
sz[v] += sz[u];
for(auto &i : keys[iu]){
if(keys[iv].find(i) == keys[iv].end()){
keys[iv].insert(i);
auto it = gph[iv].lower_bound(pi(i, -1));
while(it != gph[iv].end() && it->first == i){
canReach[iv].push_back(it->second);
it = gph[iv].erase(it);
}
}
}
for(auto &i : canReach[iu]) canReach[iv].push_back(i);
for(auto &[c, d] : gph[iu]){
if(keys[iv].find(c) != keys[iv].end()){
canReach[iv].push_back(d);
}
else gph[iv].emplace(c, d);
}
keys[iu].clear();
gph[iu].clear();
canReach[iu].clear();
idx[v] = iv;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = sz(r);
for(int i = 0; i < n; i++) keys[i].insert(r[i]);
for(int i = 0; i < sz(u); i++){
if(c[i] == r[u[i]]){
canReach[u[i]].push_back(v[i]);
} else{
gph[u[i]].emplace(c[i], v[i]);
}
if(c[i] == r[v[i]]){
canReach[v[i]].push_back(u[i]);
} else {
gph[v[i]].emplace(c[i], u[i]);
}
}
disj.init();
iota(idx, idx + MAXN, 0);
fill(sz, sz + MAXN, 1);
iota(comp, comp + MAXN, 0);
vector<int> ans(n, 1e9);
for(int i = 0; i < n; i++){
nxt[i] = i;
if(sz(canReach[i])) nxt[i] = canReach[i][0];
}
for(int i = 0; i < n; i++){
if(find(i) != i) continue;
if(i == find(nxt[i])) continue;
if(!disj.uni(i, nxt[i])){
for(int j = find(nxt[i]); find(j) != find(n); j = find(nxt[j])){
merge_to(j, n);
}
disj.uni(i, n);
nxt[n] = n;
while(sz(canReach[idx[n]]) && find(canReach[idx[n]].back()) == find(n)){
canReach[idx[n]].pop_back();
}
if(sz(canReach[idx[n]])) nxt[n] = canReach[idx[n]].back();
n++;
assert(n <= 600000);
}
}
vector<int> cnt(n);
for(int j = 0; j < sz(ans); j++){
cnt[find(j)]++;
}
fill(all(ans), 1e9);
for(int i = 0; i < sz(ans); i++){
int r = find(i);
if(find(r) == find(nxt[r])) ans[i] = cnt[r];
}
int val = *min_element(all(ans));
for(auto &i : ans){
i = (i == val);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
80024 KB |
Output is correct |
2 |
Correct |
50 ms |
80016 KB |
Output is correct |
3 |
Correct |
47 ms |
80096 KB |
Output is correct |
4 |
Correct |
47 ms |
80076 KB |
Output is correct |
5 |
Correct |
50 ms |
80056 KB |
Output is correct |
6 |
Correct |
50 ms |
80032 KB |
Output is correct |
7 |
Correct |
51 ms |
80028 KB |
Output is correct |
8 |
Correct |
47 ms |
80020 KB |
Output is correct |
9 |
Correct |
47 ms |
80064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
80024 KB |
Output is correct |
2 |
Correct |
50 ms |
80016 KB |
Output is correct |
3 |
Correct |
47 ms |
80096 KB |
Output is correct |
4 |
Correct |
47 ms |
80076 KB |
Output is correct |
5 |
Correct |
50 ms |
80056 KB |
Output is correct |
6 |
Correct |
50 ms |
80032 KB |
Output is correct |
7 |
Correct |
51 ms |
80028 KB |
Output is correct |
8 |
Correct |
47 ms |
80020 KB |
Output is correct |
9 |
Correct |
47 ms |
80064 KB |
Output is correct |
10 |
Correct |
47 ms |
80052 KB |
Output is correct |
11 |
Correct |
44 ms |
80092 KB |
Output is correct |
12 |
Correct |
53 ms |
80092 KB |
Output is correct |
13 |
Correct |
48 ms |
80068 KB |
Output is correct |
14 |
Correct |
48 ms |
80116 KB |
Output is correct |
15 |
Correct |
47 ms |
80044 KB |
Output is correct |
16 |
Correct |
49 ms |
80216 KB |
Output is correct |
17 |
Correct |
47 ms |
80076 KB |
Output is correct |
18 |
Correct |
46 ms |
80088 KB |
Output is correct |
19 |
Correct |
52 ms |
80068 KB |
Output is correct |
20 |
Correct |
51 ms |
80084 KB |
Output is correct |
21 |
Correct |
47 ms |
80068 KB |
Output is correct |
22 |
Correct |
47 ms |
80008 KB |
Output is correct |
23 |
Correct |
47 ms |
80088 KB |
Output is correct |
24 |
Correct |
50 ms |
80052 KB |
Output is correct |
25 |
Correct |
46 ms |
80068 KB |
Output is correct |
26 |
Correct |
51 ms |
80032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
80024 KB |
Output is correct |
2 |
Correct |
50 ms |
80016 KB |
Output is correct |
3 |
Correct |
47 ms |
80096 KB |
Output is correct |
4 |
Correct |
47 ms |
80076 KB |
Output is correct |
5 |
Correct |
50 ms |
80056 KB |
Output is correct |
6 |
Correct |
50 ms |
80032 KB |
Output is correct |
7 |
Correct |
51 ms |
80028 KB |
Output is correct |
8 |
Correct |
47 ms |
80020 KB |
Output is correct |
9 |
Correct |
47 ms |
80064 KB |
Output is correct |
10 |
Correct |
47 ms |
80052 KB |
Output is correct |
11 |
Correct |
44 ms |
80092 KB |
Output is correct |
12 |
Correct |
53 ms |
80092 KB |
Output is correct |
13 |
Correct |
48 ms |
80068 KB |
Output is correct |
14 |
Correct |
48 ms |
80116 KB |
Output is correct |
15 |
Correct |
47 ms |
80044 KB |
Output is correct |
16 |
Correct |
49 ms |
80216 KB |
Output is correct |
17 |
Correct |
47 ms |
80076 KB |
Output is correct |
18 |
Correct |
46 ms |
80088 KB |
Output is correct |
19 |
Correct |
52 ms |
80068 KB |
Output is correct |
20 |
Correct |
51 ms |
80084 KB |
Output is correct |
21 |
Correct |
47 ms |
80068 KB |
Output is correct |
22 |
Correct |
47 ms |
80008 KB |
Output is correct |
23 |
Correct |
47 ms |
80088 KB |
Output is correct |
24 |
Correct |
50 ms |
80052 KB |
Output is correct |
25 |
Correct |
46 ms |
80068 KB |
Output is correct |
26 |
Correct |
51 ms |
80032 KB |
Output is correct |
27 |
Correct |
49 ms |
80568 KB |
Output is correct |
28 |
Correct |
57 ms |
80484 KB |
Output is correct |
29 |
Correct |
48 ms |
80380 KB |
Output is correct |
30 |
Correct |
52 ms |
80212 KB |
Output is correct |
31 |
Correct |
53 ms |
80212 KB |
Output is correct |
32 |
Correct |
50 ms |
80268 KB |
Output is correct |
33 |
Correct |
52 ms |
80196 KB |
Output is correct |
34 |
Correct |
48 ms |
80176 KB |
Output is correct |
35 |
Correct |
48 ms |
80204 KB |
Output is correct |
36 |
Correct |
49 ms |
80308 KB |
Output is correct |
37 |
Correct |
49 ms |
80452 KB |
Output is correct |
38 |
Correct |
47 ms |
80448 KB |
Output is correct |
39 |
Correct |
53 ms |
80416 KB |
Output is correct |
40 |
Correct |
52 ms |
80304 KB |
Output is correct |
41 |
Correct |
56 ms |
80332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
80024 KB |
Output is correct |
2 |
Correct |
50 ms |
80016 KB |
Output is correct |
3 |
Correct |
47 ms |
80096 KB |
Output is correct |
4 |
Correct |
47 ms |
80076 KB |
Output is correct |
5 |
Correct |
50 ms |
80056 KB |
Output is correct |
6 |
Correct |
50 ms |
80032 KB |
Output is correct |
7 |
Correct |
51 ms |
80028 KB |
Output is correct |
8 |
Correct |
47 ms |
80020 KB |
Output is correct |
9 |
Correct |
47 ms |
80064 KB |
Output is correct |
10 |
Correct |
820 ms |
121980 KB |
Output is correct |
11 |
Correct |
1171 ms |
146092 KB |
Output is correct |
12 |
Correct |
138 ms |
89796 KB |
Output is correct |
13 |
Correct |
656 ms |
127140 KB |
Output is correct |
14 |
Correct |
375 ms |
123720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
80024 KB |
Output is correct |
2 |
Correct |
50 ms |
80016 KB |
Output is correct |
3 |
Correct |
47 ms |
80096 KB |
Output is correct |
4 |
Correct |
47 ms |
80076 KB |
Output is correct |
5 |
Correct |
50 ms |
80056 KB |
Output is correct |
6 |
Correct |
50 ms |
80032 KB |
Output is correct |
7 |
Correct |
51 ms |
80028 KB |
Output is correct |
8 |
Correct |
47 ms |
80020 KB |
Output is correct |
9 |
Correct |
47 ms |
80064 KB |
Output is correct |
10 |
Correct |
47 ms |
80052 KB |
Output is correct |
11 |
Correct |
44 ms |
80092 KB |
Output is correct |
12 |
Correct |
53 ms |
80092 KB |
Output is correct |
13 |
Correct |
48 ms |
80068 KB |
Output is correct |
14 |
Correct |
48 ms |
80116 KB |
Output is correct |
15 |
Correct |
47 ms |
80044 KB |
Output is correct |
16 |
Correct |
49 ms |
80216 KB |
Output is correct |
17 |
Correct |
47 ms |
80076 KB |
Output is correct |
18 |
Correct |
46 ms |
80088 KB |
Output is correct |
19 |
Correct |
52 ms |
80068 KB |
Output is correct |
20 |
Correct |
51 ms |
80084 KB |
Output is correct |
21 |
Correct |
47 ms |
80068 KB |
Output is correct |
22 |
Correct |
47 ms |
80008 KB |
Output is correct |
23 |
Correct |
47 ms |
80088 KB |
Output is correct |
24 |
Correct |
50 ms |
80052 KB |
Output is correct |
25 |
Correct |
46 ms |
80068 KB |
Output is correct |
26 |
Correct |
51 ms |
80032 KB |
Output is correct |
27 |
Correct |
49 ms |
80568 KB |
Output is correct |
28 |
Correct |
57 ms |
80484 KB |
Output is correct |
29 |
Correct |
48 ms |
80380 KB |
Output is correct |
30 |
Correct |
52 ms |
80212 KB |
Output is correct |
31 |
Correct |
53 ms |
80212 KB |
Output is correct |
32 |
Correct |
50 ms |
80268 KB |
Output is correct |
33 |
Correct |
52 ms |
80196 KB |
Output is correct |
34 |
Correct |
48 ms |
80176 KB |
Output is correct |
35 |
Correct |
48 ms |
80204 KB |
Output is correct |
36 |
Correct |
49 ms |
80308 KB |
Output is correct |
37 |
Correct |
49 ms |
80452 KB |
Output is correct |
38 |
Correct |
47 ms |
80448 KB |
Output is correct |
39 |
Correct |
53 ms |
80416 KB |
Output is correct |
40 |
Correct |
52 ms |
80304 KB |
Output is correct |
41 |
Correct |
56 ms |
80332 KB |
Output is correct |
42 |
Correct |
820 ms |
121980 KB |
Output is correct |
43 |
Correct |
1171 ms |
146092 KB |
Output is correct |
44 |
Correct |
138 ms |
89796 KB |
Output is correct |
45 |
Correct |
656 ms |
127140 KB |
Output is correct |
46 |
Correct |
375 ms |
123720 KB |
Output is correct |
47 |
Correct |
47 ms |
80068 KB |
Output is correct |
48 |
Correct |
52 ms |
80064 KB |
Output is correct |
49 |
Correct |
49 ms |
80068 KB |
Output is correct |
50 |
Correct |
319 ms |
121236 KB |
Output is correct |
51 |
Correct |
340 ms |
123044 KB |
Output is correct |
52 |
Correct |
317 ms |
115344 KB |
Output is correct |
53 |
Correct |
298 ms |
115296 KB |
Output is correct |
54 |
Correct |
321 ms |
115268 KB |
Output is correct |
55 |
Correct |
949 ms |
122560 KB |
Output is correct |
56 |
Correct |
357 ms |
125764 KB |
Output is correct |
57 |
Correct |
305 ms |
122320 KB |
Output is correct |
58 |
Correct |
617 ms |
130500 KB |
Output is correct |
59 |
Correct |
1454 ms |
127156 KB |
Output is correct |
60 |
Correct |
1280 ms |
127208 KB |
Output is correct |
61 |
Correct |
1154 ms |
127156 KB |
Output is correct |
62 |
Correct |
1800 ms |
125964 KB |
Output is correct |
63 |
Correct |
357 ms |
125148 KB |
Output is correct |
64 |
Correct |
53 ms |
81064 KB |
Output is correct |
65 |
Correct |
50 ms |
80920 KB |
Output is correct |
66 |
Correct |
1840 ms |
125808 KB |
Output is correct |
67 |
Correct |
79 ms |
84660 KB |
Output is correct |
68 |
Correct |
103 ms |
87612 KB |
Output is correct |
69 |
Correct |
1593 ms |
127176 KB |
Output is correct |
70 |
Correct |
174 ms |
95428 KB |
Output is correct |
71 |
Correct |
447 ms |
123528 KB |
Output is correct |
72 |
Correct |
1390 ms |
127272 KB |
Output is correct |
73 |
Correct |
1740 ms |
125676 KB |
Output is correct |