# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
436035 |
2021-06-24T06:14:08 Z |
79brue |
Keys (IOI21_keys) |
C++17 |
|
1515 ms |
140728 KB |
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
struct disjointSet{
int n;
int par[300002];
int sz[300002];
void init(int _n){
n = _n;
for(int i=0; i<=n; i++) par[i] = i, sz[i] = 1;
}
int find(int x){
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
sz[x] += sz[y];
par[y] = x;
}
} dsu;
struct Bitset{
unordered_map<int, ll> mp;
Bitset(){}
Bitset(int x){
mp[x>>6] = 1ULL << (x&63);
}
void merge(Bitset &r){
if(mp.size() > r.mp.size()){
for(auto p: r.mp){
mp[p.first] |= p.second;
}
r.mp.clear();
}
else{
for(auto p: mp){
r.mp[p.first] |= p.second;
}
mp.clear();
mp.swap(r.mp);
}
}
bool chk(int x){
return !!(mp[x>>6] & (1ULL << (x&63)));
}
};
int n;
Bitset arr[300002];
vector<pair<int, int> > link[300002];
stack<int> stk;
bool visited[300002];
bool merged[300002];
vector<int> sccVec;
void dfs1(int x){
visited[x] = 1;
for(auto &y: link[x]){
y.first = dsu.find(y.first);
if(visited[y.first] || !arr[x].chk(y.second)) continue;
dfs1(y.first);
}
stk.push(x);
}
void dfs2(int x){
visited[x] = 0;
sccVec.push_back(x);
for(auto &y: link[x]){
y.first = dsu.find(y.first);
if(!visited[y.first] || !arr[y.first].chk(y.second)) continue;
dfs2(y.first);
}
}
void makeSCC(){
for(int i=0; i<n; i++){
if(!visited[i] && !merged[i]) dfs1(i);
}
while(!stk.empty()){
int tmp = stk.top();
stk.pop();
if(!visited[tmp]) continue;
sccVec.clear();
dfs2(tmp);
for(auto x: sccVec){
if(x==tmp) continue;
arr[tmp].merge(arr[x]);
if(link[tmp].size() > link[x].size()){
for(auto p: link[x]) link[tmp].push_back(p);
link[x].clear();
link[x].shrink_to_fit();
}
else{
for(auto p: link[tmp]) link[x].push_back(p);
link[tmp].clear();
link[tmp].shrink_to_fit();
link[x].swap(link[tmp]);
}
dsu.merge(tmp, x);
merged[x] = 1;
}
}
}
bool toOther[300002];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
n = (int)r.size();
for(int i=0; i<n; i++){
arr[i] = Bitset(r[i]);
}
for(int i=0; i<(int)u.size(); i++){
link[u[i]].push_back(make_pair(v[i], c[i]));
link[v[i]].push_back(make_pair(u[i], c[i]));
}
dsu.init(n);
for(int d=0; d<=2; d++){
makeSCC();
}
for(int i=0; i<n; i++){
if(merged[i]) continue;
for(auto y: link[i]){
if(i != dsu.find(y.first) && arr[i].chk(y.second)) toOther[i] = 1;
}
}
int minSize = n+1;
for(int i=0; i<n; i++){
if(!toOther[dsu.find(i)]) minSize = min(minSize, dsu.sz[dsu.find(i)]);
}
vector<int> ans (n);
for(int i=0; i<n; i++){
ans[i] = (!toOther[dsu.find(i)] && dsu.sz[dsu.find(i)] == minSize);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23756 KB |
Output is correct |
2 |
Correct |
19 ms |
23772 KB |
Output is correct |
3 |
Correct |
22 ms |
23800 KB |
Output is correct |
4 |
Correct |
22 ms |
23844 KB |
Output is correct |
5 |
Correct |
22 ms |
23764 KB |
Output is correct |
6 |
Correct |
19 ms |
23756 KB |
Output is correct |
7 |
Correct |
17 ms |
23756 KB |
Output is correct |
8 |
Correct |
19 ms |
23844 KB |
Output is correct |
9 |
Correct |
18 ms |
23756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23756 KB |
Output is correct |
2 |
Correct |
19 ms |
23772 KB |
Output is correct |
3 |
Correct |
22 ms |
23800 KB |
Output is correct |
4 |
Correct |
22 ms |
23844 KB |
Output is correct |
5 |
Correct |
22 ms |
23764 KB |
Output is correct |
6 |
Correct |
19 ms |
23756 KB |
Output is correct |
7 |
Correct |
17 ms |
23756 KB |
Output is correct |
8 |
Correct |
19 ms |
23844 KB |
Output is correct |
9 |
Correct |
18 ms |
23756 KB |
Output is correct |
10 |
Correct |
19 ms |
23784 KB |
Output is correct |
11 |
Correct |
18 ms |
23756 KB |
Output is correct |
12 |
Correct |
21 ms |
23904 KB |
Output is correct |
13 |
Correct |
17 ms |
23708 KB |
Output is correct |
14 |
Correct |
18 ms |
23740 KB |
Output is correct |
15 |
Correct |
19 ms |
23984 KB |
Output is correct |
16 |
Correct |
18 ms |
23684 KB |
Output is correct |
17 |
Correct |
21 ms |
23800 KB |
Output is correct |
18 |
Correct |
18 ms |
23736 KB |
Output is correct |
19 |
Correct |
19 ms |
23800 KB |
Output is correct |
20 |
Correct |
17 ms |
23756 KB |
Output is correct |
21 |
Correct |
20 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23824 KB |
Output is correct |
23 |
Correct |
20 ms |
23860 KB |
Output is correct |
24 |
Correct |
19 ms |
23756 KB |
Output is correct |
25 |
Correct |
18 ms |
23820 KB |
Output is correct |
26 |
Correct |
19 ms |
23756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23756 KB |
Output is correct |
2 |
Correct |
19 ms |
23772 KB |
Output is correct |
3 |
Correct |
22 ms |
23800 KB |
Output is correct |
4 |
Correct |
22 ms |
23844 KB |
Output is correct |
5 |
Correct |
22 ms |
23764 KB |
Output is correct |
6 |
Correct |
19 ms |
23756 KB |
Output is correct |
7 |
Correct |
17 ms |
23756 KB |
Output is correct |
8 |
Correct |
19 ms |
23844 KB |
Output is correct |
9 |
Correct |
18 ms |
23756 KB |
Output is correct |
10 |
Correct |
19 ms |
23784 KB |
Output is correct |
11 |
Correct |
18 ms |
23756 KB |
Output is correct |
12 |
Correct |
21 ms |
23904 KB |
Output is correct |
13 |
Correct |
17 ms |
23708 KB |
Output is correct |
14 |
Correct |
18 ms |
23740 KB |
Output is correct |
15 |
Correct |
19 ms |
23984 KB |
Output is correct |
16 |
Correct |
18 ms |
23684 KB |
Output is correct |
17 |
Correct |
21 ms |
23800 KB |
Output is correct |
18 |
Correct |
18 ms |
23736 KB |
Output is correct |
19 |
Correct |
19 ms |
23800 KB |
Output is correct |
20 |
Correct |
17 ms |
23756 KB |
Output is correct |
21 |
Correct |
20 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23824 KB |
Output is correct |
23 |
Correct |
20 ms |
23860 KB |
Output is correct |
24 |
Correct |
19 ms |
23756 KB |
Output is correct |
25 |
Correct |
18 ms |
23820 KB |
Output is correct |
26 |
Correct |
19 ms |
23756 KB |
Output is correct |
27 |
Correct |
25 ms |
24340 KB |
Output is correct |
28 |
Correct |
20 ms |
24336 KB |
Output is correct |
29 |
Correct |
20 ms |
24268 KB |
Output is correct |
30 |
Correct |
23 ms |
24012 KB |
Output is correct |
31 |
Correct |
20 ms |
24012 KB |
Output is correct |
32 |
Correct |
20 ms |
23900 KB |
Output is correct |
33 |
Correct |
19 ms |
23920 KB |
Output is correct |
34 |
Correct |
18 ms |
24188 KB |
Output is correct |
35 |
Correct |
22 ms |
24072 KB |
Output is correct |
36 |
Correct |
19 ms |
24440 KB |
Output is correct |
37 |
Correct |
20 ms |
24408 KB |
Output is correct |
38 |
Correct |
20 ms |
24524 KB |
Output is correct |
39 |
Correct |
24 ms |
24524 KB |
Output is correct |
40 |
Correct |
19 ms |
24012 KB |
Output is correct |
41 |
Correct |
20 ms |
24168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23756 KB |
Output is correct |
2 |
Correct |
19 ms |
23772 KB |
Output is correct |
3 |
Correct |
22 ms |
23800 KB |
Output is correct |
4 |
Correct |
22 ms |
23844 KB |
Output is correct |
5 |
Correct |
22 ms |
23764 KB |
Output is correct |
6 |
Correct |
19 ms |
23756 KB |
Output is correct |
7 |
Correct |
17 ms |
23756 KB |
Output is correct |
8 |
Correct |
19 ms |
23844 KB |
Output is correct |
9 |
Correct |
18 ms |
23756 KB |
Output is correct |
10 |
Correct |
724 ms |
61844 KB |
Output is correct |
11 |
Correct |
772 ms |
95780 KB |
Output is correct |
12 |
Correct |
161 ms |
35872 KB |
Output is correct |
13 |
Correct |
755 ms |
84992 KB |
Output is correct |
14 |
Correct |
371 ms |
140728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23756 KB |
Output is correct |
2 |
Correct |
19 ms |
23772 KB |
Output is correct |
3 |
Correct |
22 ms |
23800 KB |
Output is correct |
4 |
Correct |
22 ms |
23844 KB |
Output is correct |
5 |
Correct |
22 ms |
23764 KB |
Output is correct |
6 |
Correct |
19 ms |
23756 KB |
Output is correct |
7 |
Correct |
17 ms |
23756 KB |
Output is correct |
8 |
Correct |
19 ms |
23844 KB |
Output is correct |
9 |
Correct |
18 ms |
23756 KB |
Output is correct |
10 |
Correct |
19 ms |
23784 KB |
Output is correct |
11 |
Correct |
18 ms |
23756 KB |
Output is correct |
12 |
Correct |
21 ms |
23904 KB |
Output is correct |
13 |
Correct |
17 ms |
23708 KB |
Output is correct |
14 |
Correct |
18 ms |
23740 KB |
Output is correct |
15 |
Correct |
19 ms |
23984 KB |
Output is correct |
16 |
Correct |
18 ms |
23684 KB |
Output is correct |
17 |
Correct |
21 ms |
23800 KB |
Output is correct |
18 |
Correct |
18 ms |
23736 KB |
Output is correct |
19 |
Correct |
19 ms |
23800 KB |
Output is correct |
20 |
Correct |
17 ms |
23756 KB |
Output is correct |
21 |
Correct |
20 ms |
23756 KB |
Output is correct |
22 |
Correct |
17 ms |
23824 KB |
Output is correct |
23 |
Correct |
20 ms |
23860 KB |
Output is correct |
24 |
Correct |
19 ms |
23756 KB |
Output is correct |
25 |
Correct |
18 ms |
23820 KB |
Output is correct |
26 |
Correct |
19 ms |
23756 KB |
Output is correct |
27 |
Correct |
25 ms |
24340 KB |
Output is correct |
28 |
Correct |
20 ms |
24336 KB |
Output is correct |
29 |
Correct |
20 ms |
24268 KB |
Output is correct |
30 |
Correct |
23 ms |
24012 KB |
Output is correct |
31 |
Correct |
20 ms |
24012 KB |
Output is correct |
32 |
Correct |
20 ms |
23900 KB |
Output is correct |
33 |
Correct |
19 ms |
23920 KB |
Output is correct |
34 |
Correct |
18 ms |
24188 KB |
Output is correct |
35 |
Correct |
22 ms |
24072 KB |
Output is correct |
36 |
Correct |
19 ms |
24440 KB |
Output is correct |
37 |
Correct |
20 ms |
24408 KB |
Output is correct |
38 |
Correct |
20 ms |
24524 KB |
Output is correct |
39 |
Correct |
24 ms |
24524 KB |
Output is correct |
40 |
Correct |
19 ms |
24012 KB |
Output is correct |
41 |
Correct |
20 ms |
24168 KB |
Output is correct |
42 |
Correct |
724 ms |
61844 KB |
Output is correct |
43 |
Correct |
772 ms |
95780 KB |
Output is correct |
44 |
Correct |
161 ms |
35872 KB |
Output is correct |
45 |
Correct |
755 ms |
84992 KB |
Output is correct |
46 |
Correct |
371 ms |
140728 KB |
Output is correct |
47 |
Correct |
17 ms |
23756 KB |
Output is correct |
48 |
Correct |
19 ms |
23756 KB |
Output is correct |
49 |
Correct |
19 ms |
23804 KB |
Output is correct |
50 |
Correct |
353 ms |
119584 KB |
Output is correct |
51 |
Correct |
384 ms |
119508 KB |
Output is correct |
52 |
Correct |
823 ms |
78248 KB |
Output is correct |
53 |
Correct |
818 ms |
78508 KB |
Output is correct |
54 |
Correct |
877 ms |
78292 KB |
Output is correct |
55 |
Correct |
892 ms |
78292 KB |
Output is correct |
56 |
Correct |
1515 ms |
107592 KB |
Output is correct |
57 |
Correct |
882 ms |
101564 KB |
Output is correct |
58 |
Correct |
670 ms |
92600 KB |
Output is correct |
59 |
Correct |
951 ms |
96916 KB |
Output is correct |
60 |
Correct |
945 ms |
111456 KB |
Output is correct |
61 |
Correct |
999 ms |
111608 KB |
Output is correct |
62 |
Correct |
946 ms |
70980 KB |
Output is correct |
63 |
Correct |
291 ms |
66480 KB |
Output is correct |
64 |
Correct |
25 ms |
25816 KB |
Output is correct |
65 |
Correct |
23 ms |
25804 KB |
Output is correct |
66 |
Correct |
920 ms |
70984 KB |
Output is correct |
67 |
Correct |
51 ms |
35240 KB |
Output is correct |
68 |
Correct |
83 ms |
43044 KB |
Output is correct |
69 |
Correct |
950 ms |
94176 KB |
Output is correct |
70 |
Correct |
131 ms |
62148 KB |
Output is correct |
71 |
Correct |
381 ms |
140724 KB |
Output is correct |
72 |
Correct |
875 ms |
96776 KB |
Output is correct |
73 |
Correct |
937 ms |
70980 KB |
Output is correct |