# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
593438 |
2022-07-11T07:45:06 Z |
nohaxjustsoflo |
Keys (IOI21_keys) |
C++17 |
|
1138 ms |
95980 KB |
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=3e5+5;
const int mod=998244353;
const int mxlogN=20;
const int mxK=26;
const int inf=30000;
const int K=600;
struct DSU
{
vector<int> size,p;
int comp;
void build(int n)
{
size=vector<int>(n,1);
p=vector<int>(n);
iota(p.begin(),p.end(),0);
comp=n;
}
int get(int x)
{
if(p[x]^x) p[x]=get(p[x]);
return p[x];
}
bool unite(int a, int b)
{
a=get(a),b=get(b);
if(a==b) return 0;
if(size[a]>size[b]) swap(a,b);
p[a]=b;
size[b]+=size[a];
comp--;
return 1;
}
};
int who[mxN], nex[mxN];
int WHO(int i)
{
if(who[i]^i) who[i]=WHO(who[i]);
return who[i];
}
vector<int> conn[mxN];
set<int> keys[mxN];
set<pair<int,int>> doors[mxN];
void add_door(int i, int c, int x)
{
if(keys[i].count(c)) conn[i].push_back(x);
else doors[i].insert({c,x});
}
void add_key(int i, int c)
{
if(!keys[i].count(c))
{
keys[i].insert(c);
auto it=doors[i].lower_bound({c,-1});
while(it!=doors[i].end()&&it->first==c)
{
auto jt=next(it);
conn[i].push_back(it->second);
doors[i].erase(it);
it=jt;
}
}
}
void merge(int u, int v)
{
///prebaci ove u v
///ako ovo neradi probaj sum, pa sve da prebacis
int usz=conn[u].size()+keys[u].size()+doors[u].size();
int vsz=conn[v].size()+keys[v].size()+doors[v].size();
if(usz>vsz)
{
conn[u].swap(conn[v]);
keys[u].swap(keys[v]);
doors[u].swap(doors[v]);
}
for(auto x:conn[u]) conn[v].push_back(x);
conn[u].clear();
for(auto c:keys[u]) add_key(v,c);
keys[u].clear();
for(auto par:doors[u]) add_door(v,par.first,par.second);
doors[u].clear();
}
int cnt[mxN];
bool can[mxN];
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<m; i++)
{
add_door(u[i],c[i],v[i]);
add_door(v[i],c[i],u[i]);
}
for(int i=0; i<n; i++)
{
add_key(i,r[i]);
who[i]=nex[i]=i;
}
DSU dsu; dsu.build(n);
for(int i=0; i<n; i++)
{
while(conn[i].size())
{
int j=WHO(conn[i].back());
conn[i].pop_back();
if(dsu.get(i)==dsu.get(j))
{
vector<int> vis;
while(j!=i)
{
int k=WHO(nex[j]);
who[j]=i;
vis.push_back(j);
j=k;
}
for(int j:vis) merge(j,i);
}
else
{
nex[i]=j;
dsu.unite(i,j);
break;
}
}
if(nex[i]==i) can[i]=1;
}
for(int i=0; i<n; i++) cnt[WHO(i)]++;
int mn=n+1;
for(int i=0; i<n; i++) if(can[i]) mn=min(mn,cnt[i]);
vector<int> ans(n,0);
for(int i=0; i<n; i++) if(cnt[WHO(i)]==mn&&can[WHO(i)]) ans[i]=1;
return ans;
}
/*
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m; cin >> n >> m;
vector<int> r(n),u(m),v(m),c(m);
for(int i=0; i<n; i++) cin >> r[i];
for(int i=0; i<m; i++) cin >> u[i];
for(int i=0; i<m; i++) cin >> v[i];
for(int i=0; i<m; i++) cin >> c[i];
auto ans=find_reachable(r,u,v,c);
for(auto i:ans) cout << i << " ";
cout << "\n";
}
*/
/*
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
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35504 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
18 ms |
35528 KB |
Output is correct |
6 |
Correct |
18 ms |
35444 KB |
Output is correct |
7 |
Correct |
17 ms |
35488 KB |
Output is correct |
8 |
Correct |
19 ms |
35544 KB |
Output is correct |
9 |
Correct |
19 ms |
35540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35504 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
18 ms |
35528 KB |
Output is correct |
6 |
Correct |
18 ms |
35444 KB |
Output is correct |
7 |
Correct |
17 ms |
35488 KB |
Output is correct |
8 |
Correct |
19 ms |
35544 KB |
Output is correct |
9 |
Correct |
19 ms |
35540 KB |
Output is correct |
10 |
Correct |
17 ms |
35528 KB |
Output is correct |
11 |
Correct |
17 ms |
35540 KB |
Output is correct |
12 |
Correct |
20 ms |
35552 KB |
Output is correct |
13 |
Correct |
18 ms |
35504 KB |
Output is correct |
14 |
Correct |
18 ms |
35524 KB |
Output is correct |
15 |
Correct |
18 ms |
35540 KB |
Output is correct |
16 |
Correct |
17 ms |
35480 KB |
Output is correct |
17 |
Correct |
18 ms |
35472 KB |
Output is correct |
18 |
Correct |
18 ms |
35448 KB |
Output is correct |
19 |
Correct |
18 ms |
35472 KB |
Output is correct |
20 |
Correct |
17 ms |
35552 KB |
Output is correct |
21 |
Correct |
20 ms |
35484 KB |
Output is correct |
22 |
Correct |
18 ms |
35500 KB |
Output is correct |
23 |
Correct |
18 ms |
35540 KB |
Output is correct |
24 |
Correct |
18 ms |
35520 KB |
Output is correct |
25 |
Correct |
25 ms |
35524 KB |
Output is correct |
26 |
Correct |
18 ms |
35552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35504 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
18 ms |
35528 KB |
Output is correct |
6 |
Correct |
18 ms |
35444 KB |
Output is correct |
7 |
Correct |
17 ms |
35488 KB |
Output is correct |
8 |
Correct |
19 ms |
35544 KB |
Output is correct |
9 |
Correct |
19 ms |
35540 KB |
Output is correct |
10 |
Correct |
17 ms |
35528 KB |
Output is correct |
11 |
Correct |
17 ms |
35540 KB |
Output is correct |
12 |
Correct |
20 ms |
35552 KB |
Output is correct |
13 |
Correct |
18 ms |
35504 KB |
Output is correct |
14 |
Correct |
18 ms |
35524 KB |
Output is correct |
15 |
Correct |
18 ms |
35540 KB |
Output is correct |
16 |
Correct |
17 ms |
35480 KB |
Output is correct |
17 |
Correct |
18 ms |
35472 KB |
Output is correct |
18 |
Correct |
18 ms |
35448 KB |
Output is correct |
19 |
Correct |
18 ms |
35472 KB |
Output is correct |
20 |
Correct |
17 ms |
35552 KB |
Output is correct |
21 |
Correct |
20 ms |
35484 KB |
Output is correct |
22 |
Correct |
18 ms |
35500 KB |
Output is correct |
23 |
Correct |
18 ms |
35540 KB |
Output is correct |
24 |
Correct |
18 ms |
35520 KB |
Output is correct |
25 |
Correct |
25 ms |
35524 KB |
Output is correct |
26 |
Correct |
18 ms |
35552 KB |
Output is correct |
27 |
Correct |
20 ms |
35868 KB |
Output is correct |
28 |
Correct |
19 ms |
35916 KB |
Output is correct |
29 |
Correct |
18 ms |
35852 KB |
Output is correct |
30 |
Correct |
19 ms |
35680 KB |
Output is correct |
31 |
Correct |
18 ms |
35668 KB |
Output is correct |
32 |
Correct |
26 ms |
35604 KB |
Output is correct |
33 |
Correct |
26 ms |
35668 KB |
Output is correct |
34 |
Correct |
19 ms |
35668 KB |
Output is correct |
35 |
Correct |
18 ms |
35600 KB |
Output is correct |
36 |
Correct |
18 ms |
35816 KB |
Output is correct |
37 |
Correct |
19 ms |
35812 KB |
Output is correct |
38 |
Correct |
19 ms |
35888 KB |
Output is correct |
39 |
Correct |
20 ms |
35924 KB |
Output is correct |
40 |
Correct |
19 ms |
35668 KB |
Output is correct |
41 |
Correct |
21 ms |
35796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35504 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
18 ms |
35528 KB |
Output is correct |
6 |
Correct |
18 ms |
35444 KB |
Output is correct |
7 |
Correct |
17 ms |
35488 KB |
Output is correct |
8 |
Correct |
19 ms |
35544 KB |
Output is correct |
9 |
Correct |
19 ms |
35540 KB |
Output is correct |
10 |
Correct |
564 ms |
77784 KB |
Output is correct |
11 |
Correct |
571 ms |
90596 KB |
Output is correct |
12 |
Correct |
98 ms |
46840 KB |
Output is correct |
13 |
Correct |
416 ms |
87144 KB |
Output is correct |
14 |
Correct |
245 ms |
83756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35504 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
18 ms |
35528 KB |
Output is correct |
6 |
Correct |
18 ms |
35444 KB |
Output is correct |
7 |
Correct |
17 ms |
35488 KB |
Output is correct |
8 |
Correct |
19 ms |
35544 KB |
Output is correct |
9 |
Correct |
19 ms |
35540 KB |
Output is correct |
10 |
Correct |
17 ms |
35528 KB |
Output is correct |
11 |
Correct |
17 ms |
35540 KB |
Output is correct |
12 |
Correct |
20 ms |
35552 KB |
Output is correct |
13 |
Correct |
18 ms |
35504 KB |
Output is correct |
14 |
Correct |
18 ms |
35524 KB |
Output is correct |
15 |
Correct |
18 ms |
35540 KB |
Output is correct |
16 |
Correct |
17 ms |
35480 KB |
Output is correct |
17 |
Correct |
18 ms |
35472 KB |
Output is correct |
18 |
Correct |
18 ms |
35448 KB |
Output is correct |
19 |
Correct |
18 ms |
35472 KB |
Output is correct |
20 |
Correct |
17 ms |
35552 KB |
Output is correct |
21 |
Correct |
20 ms |
35484 KB |
Output is correct |
22 |
Correct |
18 ms |
35500 KB |
Output is correct |
23 |
Correct |
18 ms |
35540 KB |
Output is correct |
24 |
Correct |
18 ms |
35520 KB |
Output is correct |
25 |
Correct |
25 ms |
35524 KB |
Output is correct |
26 |
Correct |
18 ms |
35552 KB |
Output is correct |
27 |
Correct |
20 ms |
35868 KB |
Output is correct |
28 |
Correct |
19 ms |
35916 KB |
Output is correct |
29 |
Correct |
18 ms |
35852 KB |
Output is correct |
30 |
Correct |
19 ms |
35680 KB |
Output is correct |
31 |
Correct |
18 ms |
35668 KB |
Output is correct |
32 |
Correct |
26 ms |
35604 KB |
Output is correct |
33 |
Correct |
26 ms |
35668 KB |
Output is correct |
34 |
Correct |
19 ms |
35668 KB |
Output is correct |
35 |
Correct |
18 ms |
35600 KB |
Output is correct |
36 |
Correct |
18 ms |
35816 KB |
Output is correct |
37 |
Correct |
19 ms |
35812 KB |
Output is correct |
38 |
Correct |
19 ms |
35888 KB |
Output is correct |
39 |
Correct |
20 ms |
35924 KB |
Output is correct |
40 |
Correct |
19 ms |
35668 KB |
Output is correct |
41 |
Correct |
21 ms |
35796 KB |
Output is correct |
42 |
Correct |
564 ms |
77784 KB |
Output is correct |
43 |
Correct |
571 ms |
90596 KB |
Output is correct |
44 |
Correct |
98 ms |
46840 KB |
Output is correct |
45 |
Correct |
416 ms |
87144 KB |
Output is correct |
46 |
Correct |
245 ms |
83756 KB |
Output is correct |
47 |
Correct |
19 ms |
35540 KB |
Output is correct |
48 |
Correct |
23 ms |
35524 KB |
Output is correct |
49 |
Correct |
20 ms |
35540 KB |
Output is correct |
50 |
Correct |
266 ms |
81520 KB |
Output is correct |
51 |
Correct |
300 ms |
81296 KB |
Output is correct |
52 |
Correct |
298 ms |
75248 KB |
Output is correct |
53 |
Correct |
286 ms |
75344 KB |
Output is correct |
54 |
Correct |
277 ms |
75176 KB |
Output is correct |
55 |
Correct |
623 ms |
80088 KB |
Output is correct |
56 |
Correct |
550 ms |
87928 KB |
Output is correct |
57 |
Correct |
578 ms |
95980 KB |
Output is correct |
58 |
Correct |
595 ms |
91420 KB |
Output is correct |
59 |
Correct |
1045 ms |
86012 KB |
Output is correct |
60 |
Correct |
430 ms |
85200 KB |
Output is correct |
61 |
Correct |
921 ms |
85912 KB |
Output is correct |
62 |
Correct |
1113 ms |
84212 KB |
Output is correct |
63 |
Correct |
229 ms |
83304 KB |
Output is correct |
64 |
Correct |
21 ms |
36464 KB |
Output is correct |
65 |
Correct |
21 ms |
36436 KB |
Output is correct |
66 |
Correct |
1138 ms |
83944 KB |
Output is correct |
67 |
Correct |
41 ms |
40760 KB |
Output is correct |
68 |
Correct |
58 ms |
44108 KB |
Output is correct |
69 |
Correct |
1022 ms |
86088 KB |
Output is correct |
70 |
Correct |
95 ms |
52712 KB |
Output is correct |
71 |
Correct |
248 ms |
83976 KB |
Output is correct |
72 |
Correct |
1004 ms |
86064 KB |
Output is correct |
73 |
Correct |
1097 ms |
84104 KB |
Output is correct |