# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
832658 |
2023-08-21T13:09:10 Z |
Rafi22 |
Keys (IOI21_keys) |
C++17 |
|
1071 ms |
206744 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
const int N=300007;
int rep[N];
int Find(int v)
{
if(rep[v]==v) return v;
return rep[v]=Find(rep[v]);
}
void Union(int u,int v)
{
u=Find(u),v=Find(v);
rep[u]=v;
}
set<int>keys[N];
vector<int>E[N];
set<pair<int,int>>edges[N];
int r[N];
vector<int>X[N];
vector<pair<int,int>>ans;
set<int>Q;
void Merge(int u,int v)
{
if(sz(X[u])>sz(X[v])) swap(u,v);
for(auto x:E[u]) E[v].pb(x);
for(auto x:keys[u])
{
keys[v].insert(x);
while(true)
{
pair<int,int>p=*edges[v].lower_bound({x,0});
if(p.st!=x) break;
edges[v].erase(p);
E[v].pb(p.nd);
}
}
for(auto [c,x]:edges[u])
{
if(keys[v].count(c)) E[v].pb(x);
else edges[v].insert({c,x});
}
for(auto x:X[u])
{
X[v].pb(x);
r[x]=v;
}
while(sz(E[v])>0)
{
if(r[E[v].back()]==v) E[v].pop_back();
else break;
}
}
vector<int>find_reachable(vector<int>K,vector<int>U,vector<int>V,vector<int>C)
{
int n=sz(K),m=sz(U);
for(int i=0;i<n;i++)
{
rep[i]=i;
X[i].pb(i);
r[i]=i;
keys[i].insert(K[i]);
edges[i].insert({inf,0});
}
for(int i=0;i<m;i++)
{
if(keys[U[i]].count(C[i])) E[U[i]].pb(V[i]);
else edges[U[i]].insert({C[i],V[i]});
if(keys[V[i]].count(C[i])) E[V[i]].pb(U[i]);
else edges[V[i]].insert({C[i],U[i]});
}
for(int i=0;i<n;i++)
{
if(sz(E[i])==0) ans.pb({1,i});
else
{
if(Find(i)==Find(E[i].back())) Q.insert(i);
else Union(i,E[i].back());
}
}
while(sz(Q)>0)
{
int v=*Q.begin();
Q.erase(v);
int x=v;
vector<int>C;
while(true)
{
C.pb(x);
x=r[E[r[x]].back()];
if(x==v) break;
}
for(int i=1;i<sz(C);i++) Merge(r[C[i]],r[C[i-1]]);
v=r[v];
if(sz(E[v])>0)
{
if(Find(v)==Find(r[E[v].back()])) Q.insert(v);
else Union(v,r[E[v].back()]);
}
else
{
for(auto x:X[v]) ans.pb({sz(X[v]),x});
}
}
sort(all(ans));
vector<int>res(n,0);
for(auto [k,i]:ans) if(k==ans[0].st) res[i]=1;
return res;
}
/*
int main()
{
int n,m;
cin>>n>>m;
vector<int>K(n);
for(int i=0;i<n;i++) cin>>K[i];
vector<int>U(m),V(m),C(m);
for(int i=0;i<m;i++) cin>>U[i]>>V[i]>>C[i];
vector<int>X=find_reachable(K,U,V,C);
for(auto x:X) cout<<x<<" ";
cout<<endl;
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42584 KB |
Output is correct |
2 |
Correct |
23 ms |
42596 KB |
Output is correct |
3 |
Correct |
19 ms |
42580 KB |
Output is correct |
4 |
Correct |
19 ms |
42508 KB |
Output is correct |
5 |
Correct |
19 ms |
42468 KB |
Output is correct |
6 |
Correct |
19 ms |
42580 KB |
Output is correct |
7 |
Correct |
23 ms |
42548 KB |
Output is correct |
8 |
Correct |
19 ms |
42580 KB |
Output is correct |
9 |
Correct |
19 ms |
42588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42584 KB |
Output is correct |
2 |
Correct |
23 ms |
42596 KB |
Output is correct |
3 |
Correct |
19 ms |
42580 KB |
Output is correct |
4 |
Correct |
19 ms |
42508 KB |
Output is correct |
5 |
Correct |
19 ms |
42468 KB |
Output is correct |
6 |
Correct |
19 ms |
42580 KB |
Output is correct |
7 |
Correct |
23 ms |
42548 KB |
Output is correct |
8 |
Correct |
19 ms |
42580 KB |
Output is correct |
9 |
Correct |
19 ms |
42588 KB |
Output is correct |
10 |
Correct |
22 ms |
42520 KB |
Output is correct |
11 |
Correct |
19 ms |
42588 KB |
Output is correct |
12 |
Correct |
19 ms |
42580 KB |
Output is correct |
13 |
Correct |
19 ms |
42508 KB |
Output is correct |
14 |
Correct |
19 ms |
42568 KB |
Output is correct |
15 |
Correct |
19 ms |
42584 KB |
Output is correct |
16 |
Correct |
19 ms |
42536 KB |
Output is correct |
17 |
Correct |
21 ms |
42520 KB |
Output is correct |
18 |
Correct |
19 ms |
42532 KB |
Output is correct |
19 |
Correct |
19 ms |
42460 KB |
Output is correct |
20 |
Correct |
19 ms |
42508 KB |
Output is correct |
21 |
Correct |
22 ms |
42640 KB |
Output is correct |
22 |
Correct |
19 ms |
42480 KB |
Output is correct |
23 |
Correct |
19 ms |
42580 KB |
Output is correct |
24 |
Correct |
23 ms |
42620 KB |
Output is correct |
25 |
Correct |
18 ms |
42612 KB |
Output is correct |
26 |
Correct |
19 ms |
42584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42584 KB |
Output is correct |
2 |
Correct |
23 ms |
42596 KB |
Output is correct |
3 |
Correct |
19 ms |
42580 KB |
Output is correct |
4 |
Correct |
19 ms |
42508 KB |
Output is correct |
5 |
Correct |
19 ms |
42468 KB |
Output is correct |
6 |
Correct |
19 ms |
42580 KB |
Output is correct |
7 |
Correct |
23 ms |
42548 KB |
Output is correct |
8 |
Correct |
19 ms |
42580 KB |
Output is correct |
9 |
Correct |
19 ms |
42588 KB |
Output is correct |
10 |
Correct |
22 ms |
42520 KB |
Output is correct |
11 |
Correct |
19 ms |
42588 KB |
Output is correct |
12 |
Correct |
19 ms |
42580 KB |
Output is correct |
13 |
Correct |
19 ms |
42508 KB |
Output is correct |
14 |
Correct |
19 ms |
42568 KB |
Output is correct |
15 |
Correct |
19 ms |
42584 KB |
Output is correct |
16 |
Correct |
19 ms |
42536 KB |
Output is correct |
17 |
Correct |
21 ms |
42520 KB |
Output is correct |
18 |
Correct |
19 ms |
42532 KB |
Output is correct |
19 |
Correct |
19 ms |
42460 KB |
Output is correct |
20 |
Correct |
19 ms |
42508 KB |
Output is correct |
21 |
Correct |
22 ms |
42640 KB |
Output is correct |
22 |
Correct |
19 ms |
42480 KB |
Output is correct |
23 |
Correct |
19 ms |
42580 KB |
Output is correct |
24 |
Correct |
23 ms |
42620 KB |
Output is correct |
25 |
Correct |
18 ms |
42612 KB |
Output is correct |
26 |
Correct |
19 ms |
42584 KB |
Output is correct |
27 |
Correct |
20 ms |
43096 KB |
Output is correct |
28 |
Correct |
21 ms |
43028 KB |
Output is correct |
29 |
Correct |
25 ms |
43176 KB |
Output is correct |
30 |
Correct |
21 ms |
42832 KB |
Output is correct |
31 |
Correct |
19 ms |
42708 KB |
Output is correct |
32 |
Correct |
19 ms |
42580 KB |
Output is correct |
33 |
Correct |
20 ms |
42864 KB |
Output is correct |
34 |
Correct |
20 ms |
42788 KB |
Output is correct |
35 |
Correct |
20 ms |
42736 KB |
Output is correct |
36 |
Correct |
23 ms |
43152 KB |
Output is correct |
37 |
Correct |
21 ms |
43136 KB |
Output is correct |
38 |
Correct |
21 ms |
43092 KB |
Output is correct |
39 |
Correct |
20 ms |
43144 KB |
Output is correct |
40 |
Correct |
20 ms |
42916 KB |
Output is correct |
41 |
Correct |
22 ms |
42944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42584 KB |
Output is correct |
2 |
Correct |
23 ms |
42596 KB |
Output is correct |
3 |
Correct |
19 ms |
42580 KB |
Output is correct |
4 |
Correct |
19 ms |
42508 KB |
Output is correct |
5 |
Correct |
19 ms |
42468 KB |
Output is correct |
6 |
Correct |
19 ms |
42580 KB |
Output is correct |
7 |
Correct |
23 ms |
42548 KB |
Output is correct |
8 |
Correct |
19 ms |
42580 KB |
Output is correct |
9 |
Correct |
19 ms |
42588 KB |
Output is correct |
10 |
Correct |
551 ms |
101568 KB |
Output is correct |
11 |
Correct |
685 ms |
133096 KB |
Output is correct |
12 |
Correct |
91 ms |
59304 KB |
Output is correct |
13 |
Correct |
528 ms |
126552 KB |
Output is correct |
14 |
Correct |
192 ms |
121732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42584 KB |
Output is correct |
2 |
Correct |
23 ms |
42596 KB |
Output is correct |
3 |
Correct |
19 ms |
42580 KB |
Output is correct |
4 |
Correct |
19 ms |
42508 KB |
Output is correct |
5 |
Correct |
19 ms |
42468 KB |
Output is correct |
6 |
Correct |
19 ms |
42580 KB |
Output is correct |
7 |
Correct |
23 ms |
42548 KB |
Output is correct |
8 |
Correct |
19 ms |
42580 KB |
Output is correct |
9 |
Correct |
19 ms |
42588 KB |
Output is correct |
10 |
Correct |
22 ms |
42520 KB |
Output is correct |
11 |
Correct |
19 ms |
42588 KB |
Output is correct |
12 |
Correct |
19 ms |
42580 KB |
Output is correct |
13 |
Correct |
19 ms |
42508 KB |
Output is correct |
14 |
Correct |
19 ms |
42568 KB |
Output is correct |
15 |
Correct |
19 ms |
42584 KB |
Output is correct |
16 |
Correct |
19 ms |
42536 KB |
Output is correct |
17 |
Correct |
21 ms |
42520 KB |
Output is correct |
18 |
Correct |
19 ms |
42532 KB |
Output is correct |
19 |
Correct |
19 ms |
42460 KB |
Output is correct |
20 |
Correct |
19 ms |
42508 KB |
Output is correct |
21 |
Correct |
22 ms |
42640 KB |
Output is correct |
22 |
Correct |
19 ms |
42480 KB |
Output is correct |
23 |
Correct |
19 ms |
42580 KB |
Output is correct |
24 |
Correct |
23 ms |
42620 KB |
Output is correct |
25 |
Correct |
18 ms |
42612 KB |
Output is correct |
26 |
Correct |
19 ms |
42584 KB |
Output is correct |
27 |
Correct |
20 ms |
43096 KB |
Output is correct |
28 |
Correct |
21 ms |
43028 KB |
Output is correct |
29 |
Correct |
25 ms |
43176 KB |
Output is correct |
30 |
Correct |
21 ms |
42832 KB |
Output is correct |
31 |
Correct |
19 ms |
42708 KB |
Output is correct |
32 |
Correct |
19 ms |
42580 KB |
Output is correct |
33 |
Correct |
20 ms |
42864 KB |
Output is correct |
34 |
Correct |
20 ms |
42788 KB |
Output is correct |
35 |
Correct |
20 ms |
42736 KB |
Output is correct |
36 |
Correct |
23 ms |
43152 KB |
Output is correct |
37 |
Correct |
21 ms |
43136 KB |
Output is correct |
38 |
Correct |
21 ms |
43092 KB |
Output is correct |
39 |
Correct |
20 ms |
43144 KB |
Output is correct |
40 |
Correct |
20 ms |
42916 KB |
Output is correct |
41 |
Correct |
22 ms |
42944 KB |
Output is correct |
42 |
Correct |
551 ms |
101568 KB |
Output is correct |
43 |
Correct |
685 ms |
133096 KB |
Output is correct |
44 |
Correct |
91 ms |
59304 KB |
Output is correct |
45 |
Correct |
528 ms |
126552 KB |
Output is correct |
46 |
Correct |
192 ms |
121732 KB |
Output is correct |
47 |
Correct |
18 ms |
42560 KB |
Output is correct |
48 |
Correct |
18 ms |
42580 KB |
Output is correct |
49 |
Correct |
19 ms |
42580 KB |
Output is correct |
50 |
Correct |
235 ms |
112812 KB |
Output is correct |
51 |
Correct |
248 ms |
115128 KB |
Output is correct |
52 |
Correct |
285 ms |
99288 KB |
Output is correct |
53 |
Correct |
298 ms |
99316 KB |
Output is correct |
54 |
Correct |
299 ms |
99408 KB |
Output is correct |
55 |
Correct |
651 ms |
105788 KB |
Output is correct |
56 |
Correct |
363 ms |
121032 KB |
Output is correct |
57 |
Correct |
336 ms |
119324 KB |
Output is correct |
58 |
Correct |
489 ms |
124360 KB |
Output is correct |
59 |
Correct |
852 ms |
126480 KB |
Output is correct |
60 |
Correct |
418 ms |
110284 KB |
Output is correct |
61 |
Correct |
907 ms |
129576 KB |
Output is correct |
62 |
Correct |
1052 ms |
206688 KB |
Output is correct |
63 |
Correct |
265 ms |
121972 KB |
Output is correct |
64 |
Correct |
23 ms |
43892 KB |
Output is correct |
65 |
Correct |
23 ms |
43852 KB |
Output is correct |
66 |
Correct |
1016 ms |
206580 KB |
Output is correct |
67 |
Correct |
37 ms |
50316 KB |
Output is correct |
68 |
Correct |
50 ms |
55420 KB |
Output is correct |
69 |
Correct |
908 ms |
126716 KB |
Output is correct |
70 |
Correct |
80 ms |
68564 KB |
Output is correct |
71 |
Correct |
201 ms |
122032 KB |
Output is correct |
72 |
Correct |
869 ms |
126768 KB |
Output is correct |
73 |
Correct |
1071 ms |
206744 KB |
Output is correct |