# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
752526 |
2023-06-03T06:32:38 Z |
1bin |
Keys (IOI21_keys) |
C++17 |
|
1121 ms |
158908 KB |
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
int n, m, par[NMAX], dfsn[NMAX], fin[NMAX], sz[NMAX], bad[NMAX], t, from[NMAX];
vector<int> E[NMAX];
set<int> K[NMAX];
map<int, vector<int>> mp[NMAX];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}
void Union(int a, int b){
if(K[a].size() + mp[a].size() < K[b].size() + mp[b].size()) swap(K[a], K[b]), swap(mp[a], mp[b]);
for(auto&[k, v] : mp[b]){
if(K[a].find(k) == K[a].end()) {
if(mp[a][k].size() < v.size()) swap(mp[a][k], v);
for(auto&y : v) mp[a][k].emplace_back(y);
}
else{
if(E[a].size() < v.size()) swap(E[a], v);
for(auto& y : v) E[a].emplace_back(y);
}
}
for(auto& k : K[b]) {
K[a].emplace(k);
for(int& y : mp[a][k]) E[a].emplace_back(y);
mp[a].erase(k);
}
if(E[a].size() < E[b].size()) swap(E[a], E[b]);
for(auto& e : E[b]) E[a].emplace_back(e);
E[b].clear();
sz[a] += sz[b];
par[b] = a;
bad[a] |= bad[b];
return;
}
void dfs(int x){
dfsn[x] = ++t;
while(E[x].size()){
x = find(x);
int nx = find(E[x].back()); E[x].pop_back();
if(x == nx) continue;
if(!dfsn[nx]){
from[nx] = x;
dfs(nx);
}
else if(!fin[nx]){
for(int i = x; i != nx; i = from[i]) Union(nx, i);
}
if(find(nx) != find(x)) bad[x] = 1;
}
fin[x] = 1;
return;
}
vector<int> find_reachable(vector<int>r, vector<int> u, vector<int> v, vector<int> c){
n = r.size(); m = u.size();
auto add_edge = [&](int& a, int& b, int& c){
if(r[a] == c) E[a].emplace_back(b);
else mp[a][c].emplace_back(b);
};
for(int i = 0; i < m; i++){
add_edge(u[i], v[i], c[i]);
add_edge(v[i], u[i], c[i]);
}
memset(par, -1, sizeof(par));
for(int i = 0; i < n; i++) sz[i] = 1, K[i].emplace(r[i]);
for(int i = 0; i < n; i++)
if(!dfsn[i]) dfs(i);
vector<int> res(n, 0);
int mn = n + 1;
for(int i = 0; i < n; i++) if(!bad[find(i)]) mn = min(mn, sz[find(i)]);
for(int i = 0; i < n; i++) if(!bad[find(i)] && sz[find(i)] == mn) res[i] = 1;
return res;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> r(n), u(m), v(m), c(m);
for(auto& i : r) cin >> i;
for(auto& i : u) cin >> i;
for(auto& i : v) cin >> i;
for(auto& i : c) cin >> i;
vector<int> res = find_reachable(r, u, v, c);
for(int i = 0; i < n; i++) cout << res[i] << ' ';
return 0;
}
*/
/*
test1
4 5
0 1 1 2
0 0 1 1 3
1 2 2 3 1
0 0 1 0 2
test2
7 10
0 1 1 2 2 1 2
0 0 1 1 2 3 3 4 4 5
1 2 2 3 3 4 5 5 6 6
0 0 1 0 0 1 2 0 2 1
test3
3 1
0 0 0
0 1 0
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
36692 KB |
Output is correct |
2 |
Correct |
19 ms |
36632 KB |
Output is correct |
3 |
Correct |
19 ms |
36612 KB |
Output is correct |
4 |
Correct |
19 ms |
36764 KB |
Output is correct |
5 |
Correct |
19 ms |
36724 KB |
Output is correct |
6 |
Correct |
19 ms |
36692 KB |
Output is correct |
7 |
Correct |
21 ms |
36728 KB |
Output is correct |
8 |
Correct |
18 ms |
36692 KB |
Output is correct |
9 |
Correct |
19 ms |
36736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
36692 KB |
Output is correct |
2 |
Correct |
19 ms |
36632 KB |
Output is correct |
3 |
Correct |
19 ms |
36612 KB |
Output is correct |
4 |
Correct |
19 ms |
36764 KB |
Output is correct |
5 |
Correct |
19 ms |
36724 KB |
Output is correct |
6 |
Correct |
19 ms |
36692 KB |
Output is correct |
7 |
Correct |
21 ms |
36728 KB |
Output is correct |
8 |
Correct |
18 ms |
36692 KB |
Output is correct |
9 |
Correct |
19 ms |
36736 KB |
Output is correct |
10 |
Correct |
19 ms |
36752 KB |
Output is correct |
11 |
Correct |
20 ms |
36700 KB |
Output is correct |
12 |
Correct |
18 ms |
36692 KB |
Output is correct |
13 |
Correct |
19 ms |
36692 KB |
Output is correct |
14 |
Correct |
22 ms |
36660 KB |
Output is correct |
15 |
Correct |
19 ms |
36764 KB |
Output is correct |
16 |
Correct |
18 ms |
36728 KB |
Output is correct |
17 |
Correct |
19 ms |
36692 KB |
Output is correct |
18 |
Correct |
17 ms |
36628 KB |
Output is correct |
19 |
Correct |
22 ms |
36632 KB |
Output is correct |
20 |
Correct |
18 ms |
36692 KB |
Output is correct |
21 |
Correct |
18 ms |
36692 KB |
Output is correct |
22 |
Correct |
18 ms |
36664 KB |
Output is correct |
23 |
Correct |
17 ms |
36684 KB |
Output is correct |
24 |
Correct |
18 ms |
36740 KB |
Output is correct |
25 |
Correct |
19 ms |
36692 KB |
Output is correct |
26 |
Correct |
19 ms |
36820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
36692 KB |
Output is correct |
2 |
Correct |
19 ms |
36632 KB |
Output is correct |
3 |
Correct |
19 ms |
36612 KB |
Output is correct |
4 |
Correct |
19 ms |
36764 KB |
Output is correct |
5 |
Correct |
19 ms |
36724 KB |
Output is correct |
6 |
Correct |
19 ms |
36692 KB |
Output is correct |
7 |
Correct |
21 ms |
36728 KB |
Output is correct |
8 |
Correct |
18 ms |
36692 KB |
Output is correct |
9 |
Correct |
19 ms |
36736 KB |
Output is correct |
10 |
Correct |
19 ms |
36752 KB |
Output is correct |
11 |
Correct |
20 ms |
36700 KB |
Output is correct |
12 |
Correct |
18 ms |
36692 KB |
Output is correct |
13 |
Correct |
19 ms |
36692 KB |
Output is correct |
14 |
Correct |
22 ms |
36660 KB |
Output is correct |
15 |
Correct |
19 ms |
36764 KB |
Output is correct |
16 |
Correct |
18 ms |
36728 KB |
Output is correct |
17 |
Correct |
19 ms |
36692 KB |
Output is correct |
18 |
Correct |
17 ms |
36628 KB |
Output is correct |
19 |
Correct |
22 ms |
36632 KB |
Output is correct |
20 |
Correct |
18 ms |
36692 KB |
Output is correct |
21 |
Correct |
18 ms |
36692 KB |
Output is correct |
22 |
Correct |
18 ms |
36664 KB |
Output is correct |
23 |
Correct |
17 ms |
36684 KB |
Output is correct |
24 |
Correct |
18 ms |
36740 KB |
Output is correct |
25 |
Correct |
19 ms |
36692 KB |
Output is correct |
26 |
Correct |
19 ms |
36820 KB |
Output is correct |
27 |
Correct |
19 ms |
37284 KB |
Output is correct |
28 |
Correct |
20 ms |
37204 KB |
Output is correct |
29 |
Correct |
20 ms |
37252 KB |
Output is correct |
30 |
Correct |
20 ms |
37076 KB |
Output is correct |
31 |
Correct |
19 ms |
36936 KB |
Output is correct |
32 |
Correct |
22 ms |
36772 KB |
Output is correct |
33 |
Correct |
23 ms |
36948 KB |
Output is correct |
34 |
Correct |
20 ms |
36948 KB |
Output is correct |
35 |
Correct |
20 ms |
37024 KB |
Output is correct |
36 |
Correct |
21 ms |
37336 KB |
Output is correct |
37 |
Correct |
20 ms |
37332 KB |
Output is correct |
38 |
Correct |
20 ms |
37332 KB |
Output is correct |
39 |
Correct |
22 ms |
37356 KB |
Output is correct |
40 |
Correct |
24 ms |
36948 KB |
Output is correct |
41 |
Correct |
21 ms |
37204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
36692 KB |
Output is correct |
2 |
Correct |
19 ms |
36632 KB |
Output is correct |
3 |
Correct |
19 ms |
36612 KB |
Output is correct |
4 |
Correct |
19 ms |
36764 KB |
Output is correct |
5 |
Correct |
19 ms |
36724 KB |
Output is correct |
6 |
Correct |
19 ms |
36692 KB |
Output is correct |
7 |
Correct |
21 ms |
36728 KB |
Output is correct |
8 |
Correct |
18 ms |
36692 KB |
Output is correct |
9 |
Correct |
19 ms |
36736 KB |
Output is correct |
10 |
Correct |
610 ms |
101604 KB |
Output is correct |
11 |
Correct |
330 ms |
78552 KB |
Output is correct |
12 |
Correct |
97 ms |
51676 KB |
Output is correct |
13 |
Correct |
430 ms |
103748 KB |
Output is correct |
14 |
Correct |
203 ms |
100140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
36692 KB |
Output is correct |
2 |
Correct |
19 ms |
36632 KB |
Output is correct |
3 |
Correct |
19 ms |
36612 KB |
Output is correct |
4 |
Correct |
19 ms |
36764 KB |
Output is correct |
5 |
Correct |
19 ms |
36724 KB |
Output is correct |
6 |
Correct |
19 ms |
36692 KB |
Output is correct |
7 |
Correct |
21 ms |
36728 KB |
Output is correct |
8 |
Correct |
18 ms |
36692 KB |
Output is correct |
9 |
Correct |
19 ms |
36736 KB |
Output is correct |
10 |
Correct |
19 ms |
36752 KB |
Output is correct |
11 |
Correct |
20 ms |
36700 KB |
Output is correct |
12 |
Correct |
18 ms |
36692 KB |
Output is correct |
13 |
Correct |
19 ms |
36692 KB |
Output is correct |
14 |
Correct |
22 ms |
36660 KB |
Output is correct |
15 |
Correct |
19 ms |
36764 KB |
Output is correct |
16 |
Correct |
18 ms |
36728 KB |
Output is correct |
17 |
Correct |
19 ms |
36692 KB |
Output is correct |
18 |
Correct |
17 ms |
36628 KB |
Output is correct |
19 |
Correct |
22 ms |
36632 KB |
Output is correct |
20 |
Correct |
18 ms |
36692 KB |
Output is correct |
21 |
Correct |
18 ms |
36692 KB |
Output is correct |
22 |
Correct |
18 ms |
36664 KB |
Output is correct |
23 |
Correct |
17 ms |
36684 KB |
Output is correct |
24 |
Correct |
18 ms |
36740 KB |
Output is correct |
25 |
Correct |
19 ms |
36692 KB |
Output is correct |
26 |
Correct |
19 ms |
36820 KB |
Output is correct |
27 |
Correct |
19 ms |
37284 KB |
Output is correct |
28 |
Correct |
20 ms |
37204 KB |
Output is correct |
29 |
Correct |
20 ms |
37252 KB |
Output is correct |
30 |
Correct |
20 ms |
37076 KB |
Output is correct |
31 |
Correct |
19 ms |
36936 KB |
Output is correct |
32 |
Correct |
22 ms |
36772 KB |
Output is correct |
33 |
Correct |
23 ms |
36948 KB |
Output is correct |
34 |
Correct |
20 ms |
36948 KB |
Output is correct |
35 |
Correct |
20 ms |
37024 KB |
Output is correct |
36 |
Correct |
21 ms |
37336 KB |
Output is correct |
37 |
Correct |
20 ms |
37332 KB |
Output is correct |
38 |
Correct |
20 ms |
37332 KB |
Output is correct |
39 |
Correct |
22 ms |
37356 KB |
Output is correct |
40 |
Correct |
24 ms |
36948 KB |
Output is correct |
41 |
Correct |
21 ms |
37204 KB |
Output is correct |
42 |
Correct |
610 ms |
101604 KB |
Output is correct |
43 |
Correct |
330 ms |
78552 KB |
Output is correct |
44 |
Correct |
97 ms |
51676 KB |
Output is correct |
45 |
Correct |
430 ms |
103748 KB |
Output is correct |
46 |
Correct |
203 ms |
100140 KB |
Output is correct |
47 |
Correct |
18 ms |
36608 KB |
Output is correct |
48 |
Correct |
19 ms |
36692 KB |
Output is correct |
49 |
Correct |
19 ms |
36692 KB |
Output is correct |
50 |
Correct |
220 ms |
88344 KB |
Output is correct |
51 |
Correct |
194 ms |
75672 KB |
Output is correct |
52 |
Correct |
277 ms |
93004 KB |
Output is correct |
53 |
Correct |
257 ms |
93008 KB |
Output is correct |
54 |
Correct |
260 ms |
93084 KB |
Output is correct |
55 |
Correct |
611 ms |
115852 KB |
Output is correct |
56 |
Correct |
376 ms |
116260 KB |
Output is correct |
57 |
Correct |
256 ms |
107048 KB |
Output is correct |
58 |
Correct |
562 ms |
116152 KB |
Output is correct |
59 |
Correct |
966 ms |
136868 KB |
Output is correct |
60 |
Correct |
752 ms |
133968 KB |
Output is correct |
61 |
Correct |
764 ms |
134384 KB |
Output is correct |
62 |
Correct |
889 ms |
158828 KB |
Output is correct |
63 |
Correct |
262 ms |
108248 KB |
Output is correct |
64 |
Correct |
23 ms |
37884 KB |
Output is correct |
65 |
Correct |
26 ms |
37836 KB |
Output is correct |
66 |
Correct |
807 ms |
158908 KB |
Output is correct |
67 |
Correct |
40 ms |
43596 KB |
Output is correct |
68 |
Correct |
63 ms |
48340 KB |
Output is correct |
69 |
Correct |
1084 ms |
138056 KB |
Output is correct |
70 |
Correct |
93 ms |
59812 KB |
Output is correct |
71 |
Correct |
224 ms |
106240 KB |
Output is correct |
72 |
Correct |
1121 ms |
137984 KB |
Output is correct |
73 |
Correct |
851 ms |
158776 KB |
Output is correct |