# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
441217 |
2021-07-04T17:11:32 Z |
fcmalkcin |
Keys (IOI21_keys) |
C++17 |
|
1376 ms |
161480 KB |
#include "keys.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
mt19937 rnd(20041015);
#define fir first
#define sec second
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
namespace wasa855
{
#define N 300005
int fa[N],n;
set<int> keys[N],G[N];
set<pii> H[N];
void att(int u,int v,int col)
{
if(u==v) return ;
if(keys[u].find(col)!=keys[u].end()) G[u].insert(v);
else H[u].emplace(col,v);
}
int find(int u) {return fa[u]==u?u:fa[u]=find(fa[u]);}
void merge(int u,int v)
{
u=find(u),v=find(v);
if(u==v) return ;
// printf("merge %d %d\n",u,v);
fa[v]=u;
// if(keys[u].size()<keys[v].size()) swap(keys[u],keys[v]);
// if(G[u].size()<G[v].size()) swap(G[u],G[v]);
// if(H[u].size()<H[v].size()) swap(H[u],H[v]);
if(keys[u].size()+G[u].size()+H[u].size()<keys[v].size()+G[v].size()+H[v].size()) swap(keys[u],keys[v]),swap(G[u],G[v]),swap(H[u],H[v]);
for(int i:G[v]) G[u].insert(i);
for(int i:keys[v])
{
auto pos=H[u].lower_bound({i,0});
while(pos!=H[u].end()&&pos->fir==i)
{
G[u].insert(pos->sec);
pos=H[u].erase(pos);
}
keys[u].insert(i);
}
for(auto [c,v]:H[v]) att(u,find(v),c);
// printf("out\n");
}
int vis[N],st[N],tp;
void popfront(int u)
{
// printf("^ in %d\n",u);
while(!G[u].empty())
{
int val=*G[u].begin();
if(val!=find(val)&&find(val)!=u) G[u].insert(find(val)),G[u].erase(val);
else if(find(val)==u) G[u].erase(val);
else break;
}
// printf("out\n");
}
void work(int u)
{
st[++tp]=u,vis[u]=1;
while(tp)
{
popfront(u);
if(G[u].empty())
{
vis[st[tp--]]=2;
u=st[tp];
continue;
}
int v=*G[u].begin();
G[u].erase(v);
// printf("^ %d %d\n",u,v);
if(vis[v]==2) continue;
if(vis[v]==1)
{
while(st[tp]!=v) merge(v,st[tp]),vis[st[tp--]]=0;
u=find(st[tp]);
}
if(vis[v]==0)
{
st[++tp]=v,vis[v]=1;
u=v;
}
}
}
vector<int> Main(vector<int> a,vector<int> u,vector<int> v,vector<int> c)
{
n=a.size();
for(int i=0;i<n;i++) fa[i]=i,keys[i].insert(a[i]);
for(int i=0;i<(int)u.size();i++) att(u[i],v[i],c[i]),att(v[i],u[i],c[i]);
for(int i=0;i<n;i++) if(!vis[i]) work(i);
// for(int i=0;i<n;i++) printf("%d%c",find(i)," \n"[i==n-1]);
vector<int> siz(n),dgr(n);
for(int i=0;i<n;i++) siz[find(i)]++;
for(int i=0;i<(int)u.size();i++)
{
u[i]=find(u[i]),v[i]=find(v[i]);
if(u[i]==v[i]) continue;
if(keys[u[i]].find(c[i])!=keys[u[i]].end()) dgr[u[i]]++;
if(keys[v[i]].find(c[i])!=keys[v[i]].end()) dgr[v[i]]++;
}
// print(dgr);
int mn=inf;
for(int i=0;i<n;i++) if(find(i)==i&&!dgr[i]) mn=min(mn,siz[i]);
vector<int> ans(n);
for(int i=0;i<n;i++)
{
int u=find(i);
if(!dgr[u]&&siz[u]==mn) ans[i]=1;
}
return ans;
}
};
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
return wasa855::Main(r,u,v,c);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42572 KB |
Output is correct |
2 |
Correct |
22 ms |
42528 KB |
Output is correct |
3 |
Correct |
22 ms |
42576 KB |
Output is correct |
4 |
Correct |
23 ms |
42564 KB |
Output is correct |
5 |
Correct |
22 ms |
42516 KB |
Output is correct |
6 |
Correct |
22 ms |
42608 KB |
Output is correct |
7 |
Correct |
22 ms |
42484 KB |
Output is correct |
8 |
Correct |
23 ms |
42612 KB |
Output is correct |
9 |
Correct |
23 ms |
42572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42572 KB |
Output is correct |
2 |
Correct |
22 ms |
42528 KB |
Output is correct |
3 |
Correct |
22 ms |
42576 KB |
Output is correct |
4 |
Correct |
23 ms |
42564 KB |
Output is correct |
5 |
Correct |
22 ms |
42516 KB |
Output is correct |
6 |
Correct |
22 ms |
42608 KB |
Output is correct |
7 |
Correct |
22 ms |
42484 KB |
Output is correct |
8 |
Correct |
23 ms |
42612 KB |
Output is correct |
9 |
Correct |
23 ms |
42572 KB |
Output is correct |
10 |
Correct |
22 ms |
42624 KB |
Output is correct |
11 |
Correct |
23 ms |
42584 KB |
Output is correct |
12 |
Correct |
22 ms |
42620 KB |
Output is correct |
13 |
Correct |
22 ms |
42492 KB |
Output is correct |
14 |
Correct |
22 ms |
42580 KB |
Output is correct |
15 |
Correct |
23 ms |
42572 KB |
Output is correct |
16 |
Correct |
22 ms |
42572 KB |
Output is correct |
17 |
Correct |
22 ms |
42584 KB |
Output is correct |
18 |
Correct |
23 ms |
42568 KB |
Output is correct |
19 |
Correct |
22 ms |
42564 KB |
Output is correct |
20 |
Correct |
23 ms |
42516 KB |
Output is correct |
21 |
Correct |
26 ms |
42520 KB |
Output is correct |
22 |
Correct |
23 ms |
42580 KB |
Output is correct |
23 |
Correct |
22 ms |
42572 KB |
Output is correct |
24 |
Correct |
22 ms |
42572 KB |
Output is correct |
25 |
Correct |
22 ms |
42572 KB |
Output is correct |
26 |
Correct |
22 ms |
42572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42572 KB |
Output is correct |
2 |
Correct |
22 ms |
42528 KB |
Output is correct |
3 |
Correct |
22 ms |
42576 KB |
Output is correct |
4 |
Correct |
23 ms |
42564 KB |
Output is correct |
5 |
Correct |
22 ms |
42516 KB |
Output is correct |
6 |
Correct |
22 ms |
42608 KB |
Output is correct |
7 |
Correct |
22 ms |
42484 KB |
Output is correct |
8 |
Correct |
23 ms |
42612 KB |
Output is correct |
9 |
Correct |
23 ms |
42572 KB |
Output is correct |
10 |
Correct |
22 ms |
42624 KB |
Output is correct |
11 |
Correct |
23 ms |
42584 KB |
Output is correct |
12 |
Correct |
22 ms |
42620 KB |
Output is correct |
13 |
Correct |
22 ms |
42492 KB |
Output is correct |
14 |
Correct |
22 ms |
42580 KB |
Output is correct |
15 |
Correct |
23 ms |
42572 KB |
Output is correct |
16 |
Correct |
22 ms |
42572 KB |
Output is correct |
17 |
Correct |
22 ms |
42584 KB |
Output is correct |
18 |
Correct |
23 ms |
42568 KB |
Output is correct |
19 |
Correct |
22 ms |
42564 KB |
Output is correct |
20 |
Correct |
23 ms |
42516 KB |
Output is correct |
21 |
Correct |
26 ms |
42520 KB |
Output is correct |
22 |
Correct |
23 ms |
42580 KB |
Output is correct |
23 |
Correct |
22 ms |
42572 KB |
Output is correct |
24 |
Correct |
22 ms |
42572 KB |
Output is correct |
25 |
Correct |
22 ms |
42572 KB |
Output is correct |
26 |
Correct |
22 ms |
42572 KB |
Output is correct |
27 |
Correct |
24 ms |
43080 KB |
Output is correct |
28 |
Correct |
24 ms |
42956 KB |
Output is correct |
29 |
Correct |
26 ms |
43032 KB |
Output is correct |
30 |
Correct |
24 ms |
42752 KB |
Output is correct |
31 |
Correct |
24 ms |
42716 KB |
Output is correct |
32 |
Correct |
24 ms |
42616 KB |
Output is correct |
33 |
Correct |
24 ms |
42684 KB |
Output is correct |
34 |
Correct |
24 ms |
42764 KB |
Output is correct |
35 |
Correct |
24 ms |
42720 KB |
Output is correct |
36 |
Correct |
25 ms |
43076 KB |
Output is correct |
37 |
Correct |
25 ms |
43056 KB |
Output is correct |
38 |
Correct |
26 ms |
43212 KB |
Output is correct |
39 |
Correct |
28 ms |
43036 KB |
Output is correct |
40 |
Correct |
24 ms |
42724 KB |
Output is correct |
41 |
Correct |
27 ms |
42968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42572 KB |
Output is correct |
2 |
Correct |
22 ms |
42528 KB |
Output is correct |
3 |
Correct |
22 ms |
42576 KB |
Output is correct |
4 |
Correct |
23 ms |
42564 KB |
Output is correct |
5 |
Correct |
22 ms |
42516 KB |
Output is correct |
6 |
Correct |
22 ms |
42608 KB |
Output is correct |
7 |
Correct |
22 ms |
42484 KB |
Output is correct |
8 |
Correct |
23 ms |
42612 KB |
Output is correct |
9 |
Correct |
23 ms |
42572 KB |
Output is correct |
10 |
Correct |
725 ms |
91516 KB |
Output is correct |
11 |
Correct |
720 ms |
104900 KB |
Output is correct |
12 |
Correct |
116 ms |
54340 KB |
Output is correct |
13 |
Correct |
510 ms |
99924 KB |
Output is correct |
14 |
Correct |
301 ms |
104884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
42572 KB |
Output is correct |
2 |
Correct |
22 ms |
42528 KB |
Output is correct |
3 |
Correct |
22 ms |
42576 KB |
Output is correct |
4 |
Correct |
23 ms |
42564 KB |
Output is correct |
5 |
Correct |
22 ms |
42516 KB |
Output is correct |
6 |
Correct |
22 ms |
42608 KB |
Output is correct |
7 |
Correct |
22 ms |
42484 KB |
Output is correct |
8 |
Correct |
23 ms |
42612 KB |
Output is correct |
9 |
Correct |
23 ms |
42572 KB |
Output is correct |
10 |
Correct |
22 ms |
42624 KB |
Output is correct |
11 |
Correct |
23 ms |
42584 KB |
Output is correct |
12 |
Correct |
22 ms |
42620 KB |
Output is correct |
13 |
Correct |
22 ms |
42492 KB |
Output is correct |
14 |
Correct |
22 ms |
42580 KB |
Output is correct |
15 |
Correct |
23 ms |
42572 KB |
Output is correct |
16 |
Correct |
22 ms |
42572 KB |
Output is correct |
17 |
Correct |
22 ms |
42584 KB |
Output is correct |
18 |
Correct |
23 ms |
42568 KB |
Output is correct |
19 |
Correct |
22 ms |
42564 KB |
Output is correct |
20 |
Correct |
23 ms |
42516 KB |
Output is correct |
21 |
Correct |
26 ms |
42520 KB |
Output is correct |
22 |
Correct |
23 ms |
42580 KB |
Output is correct |
23 |
Correct |
22 ms |
42572 KB |
Output is correct |
24 |
Correct |
22 ms |
42572 KB |
Output is correct |
25 |
Correct |
22 ms |
42572 KB |
Output is correct |
26 |
Correct |
22 ms |
42572 KB |
Output is correct |
27 |
Correct |
24 ms |
43080 KB |
Output is correct |
28 |
Correct |
24 ms |
42956 KB |
Output is correct |
29 |
Correct |
26 ms |
43032 KB |
Output is correct |
30 |
Correct |
24 ms |
42752 KB |
Output is correct |
31 |
Correct |
24 ms |
42716 KB |
Output is correct |
32 |
Correct |
24 ms |
42616 KB |
Output is correct |
33 |
Correct |
24 ms |
42684 KB |
Output is correct |
34 |
Correct |
24 ms |
42764 KB |
Output is correct |
35 |
Correct |
24 ms |
42720 KB |
Output is correct |
36 |
Correct |
25 ms |
43076 KB |
Output is correct |
37 |
Correct |
25 ms |
43056 KB |
Output is correct |
38 |
Correct |
26 ms |
43212 KB |
Output is correct |
39 |
Correct |
28 ms |
43036 KB |
Output is correct |
40 |
Correct |
24 ms |
42724 KB |
Output is correct |
41 |
Correct |
27 ms |
42968 KB |
Output is correct |
42 |
Correct |
725 ms |
91516 KB |
Output is correct |
43 |
Correct |
720 ms |
104900 KB |
Output is correct |
44 |
Correct |
116 ms |
54340 KB |
Output is correct |
45 |
Correct |
510 ms |
99924 KB |
Output is correct |
46 |
Correct |
301 ms |
104884 KB |
Output is correct |
47 |
Correct |
23 ms |
42576 KB |
Output is correct |
48 |
Correct |
23 ms |
42476 KB |
Output is correct |
49 |
Correct |
23 ms |
42472 KB |
Output is correct |
50 |
Correct |
304 ms |
101332 KB |
Output is correct |
51 |
Correct |
369 ms |
108836 KB |
Output is correct |
52 |
Correct |
384 ms |
89092 KB |
Output is correct |
53 |
Correct |
388 ms |
89048 KB |
Output is correct |
54 |
Correct |
402 ms |
89028 KB |
Output is correct |
55 |
Correct |
902 ms |
99344 KB |
Output is correct |
56 |
Correct |
704 ms |
112808 KB |
Output is correct |
57 |
Correct |
683 ms |
112704 KB |
Output is correct |
58 |
Correct |
686 ms |
112752 KB |
Output is correct |
59 |
Correct |
1376 ms |
115964 KB |
Output is correct |
60 |
Correct |
1227 ms |
117316 KB |
Output is correct |
61 |
Correct |
1240 ms |
117572 KB |
Output is correct |
62 |
Correct |
971 ms |
161480 KB |
Output is correct |
63 |
Correct |
285 ms |
100820 KB |
Output is correct |
64 |
Correct |
27 ms |
43680 KB |
Output is correct |
65 |
Correct |
27 ms |
43596 KB |
Output is correct |
66 |
Correct |
982 ms |
160692 KB |
Output is correct |
67 |
Correct |
52 ms |
49340 KB |
Output is correct |
68 |
Correct |
70 ms |
53828 KB |
Output is correct |
69 |
Correct |
1295 ms |
122144 KB |
Output is correct |
70 |
Correct |
120 ms |
65220 KB |
Output is correct |
71 |
Correct |
305 ms |
110788 KB |
Output is correct |
72 |
Correct |
1352 ms |
116196 KB |
Output is correct |
73 |
Correct |
974 ms |
161084 KB |
Output is correct |