# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
825276 |
2023-08-14T16:37:22 Z |
arnold518 |
Keys (IOI21_keys) |
C++17 |
|
913 ms |
197744 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
int N, M;
int R[MAXN+10];
int ans[MAXN+10];
set<pii> adj[MAXN+10];
vector<pii> adj2[MAXN+10];
set<int> S[MAXN+10];
int par[MAXN+10];
int vis[MAXN+10];
bool dead[MAXN+10];
struct UF
{
int par[MAXN+10];
int Find(int x)
{
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
x=Find(x); y=Find(y);
par[x]=y;
}
void init()
{
for(int i=1; i<=N; i++) par[i]=i;
}
}uf, uf2;
int cnt[MAXN+10];
vector<int> find_reachable(vector<int> _R, vector<int> _U, vector<int> _V, vector<int> _C)
{
N=_R.size(); M=_U.size();
for(int i=1; i<=N; i++) R[i]=_R[i-1]+1;
for(int i=1; i<=M; i++)
{
int u=_U[i-1]+1, v=_V[i-1]+1, w=_C[i-1]+1;
if(R[u]!=w) adj[u].insert({w, v});
else adj2[u].push_back({w, v});
if(R[v]!=w) adj[v].insert({w, u});
else adj2[v].push_back({w, u});
}
uf.init(); uf2.init();
for(int i=1; i<=N; i++)
{
S[i].insert(R[i]);
if(!adj2[i].empty())
{
par[i]=adj2[i].back().second;
uf.Union(i, par[i]);
}
}
queue<int> Q;
for(int i=1; i<=N; i++)
{
int now=i;
while(1)
{
if(vis[now]) break;
vis[now]=i;
if(par[now]==0) break;
now=par[now];
}
if(par[now]!=0 && vis[now]==i) Q.push(now);
}
while(!Q.empty())
{
int now=Q.front(); Q.pop();
now=uf2.Find(now);
vector<int> V;
for(int i=par[now]; i!=now; i=uf2.Find(par[i])) V.push_back(i);
for(auto it : V)
{
if(adj[now].size()+adj2[now].size()+S[now].size()<adj[it].size()+adj2[it].size()+S[it].size()) swap(now, it);
for(auto jt : adj2[it]) adj2[now].push_back(jt);
for(auto jt : adj[it])
{
auto pt=S[now].lower_bound(jt.first);
if(pt!=S[now].end() && *pt==jt.first) adj2[now].push_back(jt);
else adj[now].insert(jt);
}
for(auto jt : S[it])
{
for(auto pt=adj[now].lower_bound({jt, 0}); pt!=adj[now].end() && pt->first==jt; pt=adj[now].erase(pt)) adj2[now].push_back(*pt);
S[now].insert(jt);
}
uf2.Union(it, now);
dead[it]=true;
}
while(!adj2[now].empty() && uf2.Find(adj2[now].back().second)==now) adj2[now].pop_back();
if(!adj2[now].empty())
{
assert(S[now].count(adj2[now].back().first));
par[now]=uf2.Find(adj2[now].back().second);
if(uf.Find(now)==uf.Find(par[now])) Q.push(now);
else uf.Union(now, par[now]);
}
else par[now]=0;
}
for(int i=1; i<=N; i++) cnt[uf2.Find(i)]++;
int val=N;
set<int> SS;
for(int i=1; i<=N; i++) if(par[uf2.Find(i)]==0) val=min(val, cnt[uf2.Find(i)]);
for(int i=1; i<=N; i++) if(par[uf2.Find(i)]==0 && cnt[uf2.Find(i)]==val) SS.insert(uf2.Find(i));
for(int i=1; i<=N; i++) if(SS.count(uf2.Find(i))) ans[i]=1;
return vector<int>(ans+1, ans+N+1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35544 KB |
Output is correct |
2 |
Correct |
16 ms |
35480 KB |
Output is correct |
3 |
Correct |
15 ms |
35452 KB |
Output is correct |
4 |
Correct |
15 ms |
35612 KB |
Output is correct |
5 |
Correct |
15 ms |
35540 KB |
Output is correct |
6 |
Correct |
16 ms |
35548 KB |
Output is correct |
7 |
Correct |
15 ms |
35516 KB |
Output is correct |
8 |
Correct |
19 ms |
35528 KB |
Output is correct |
9 |
Correct |
15 ms |
35552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35544 KB |
Output is correct |
2 |
Correct |
16 ms |
35480 KB |
Output is correct |
3 |
Correct |
15 ms |
35452 KB |
Output is correct |
4 |
Correct |
15 ms |
35612 KB |
Output is correct |
5 |
Correct |
15 ms |
35540 KB |
Output is correct |
6 |
Correct |
16 ms |
35548 KB |
Output is correct |
7 |
Correct |
15 ms |
35516 KB |
Output is correct |
8 |
Correct |
19 ms |
35528 KB |
Output is correct |
9 |
Correct |
15 ms |
35552 KB |
Output is correct |
10 |
Correct |
14 ms |
35552 KB |
Output is correct |
11 |
Correct |
15 ms |
35520 KB |
Output is correct |
12 |
Correct |
14 ms |
35540 KB |
Output is correct |
13 |
Correct |
14 ms |
35540 KB |
Output is correct |
14 |
Correct |
15 ms |
35540 KB |
Output is correct |
15 |
Correct |
16 ms |
35560 KB |
Output is correct |
16 |
Correct |
15 ms |
35544 KB |
Output is correct |
17 |
Correct |
19 ms |
35656 KB |
Output is correct |
18 |
Correct |
15 ms |
35540 KB |
Output is correct |
19 |
Correct |
15 ms |
35540 KB |
Output is correct |
20 |
Correct |
15 ms |
35512 KB |
Output is correct |
21 |
Correct |
15 ms |
35612 KB |
Output is correct |
22 |
Correct |
14 ms |
35472 KB |
Output is correct |
23 |
Correct |
15 ms |
35512 KB |
Output is correct |
24 |
Correct |
16 ms |
35544 KB |
Output is correct |
25 |
Correct |
15 ms |
35556 KB |
Output is correct |
26 |
Correct |
15 ms |
35548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35544 KB |
Output is correct |
2 |
Correct |
16 ms |
35480 KB |
Output is correct |
3 |
Correct |
15 ms |
35452 KB |
Output is correct |
4 |
Correct |
15 ms |
35612 KB |
Output is correct |
5 |
Correct |
15 ms |
35540 KB |
Output is correct |
6 |
Correct |
16 ms |
35548 KB |
Output is correct |
7 |
Correct |
15 ms |
35516 KB |
Output is correct |
8 |
Correct |
19 ms |
35528 KB |
Output is correct |
9 |
Correct |
15 ms |
35552 KB |
Output is correct |
10 |
Correct |
14 ms |
35552 KB |
Output is correct |
11 |
Correct |
15 ms |
35520 KB |
Output is correct |
12 |
Correct |
14 ms |
35540 KB |
Output is correct |
13 |
Correct |
14 ms |
35540 KB |
Output is correct |
14 |
Correct |
15 ms |
35540 KB |
Output is correct |
15 |
Correct |
16 ms |
35560 KB |
Output is correct |
16 |
Correct |
15 ms |
35544 KB |
Output is correct |
17 |
Correct |
19 ms |
35656 KB |
Output is correct |
18 |
Correct |
15 ms |
35540 KB |
Output is correct |
19 |
Correct |
15 ms |
35540 KB |
Output is correct |
20 |
Correct |
15 ms |
35512 KB |
Output is correct |
21 |
Correct |
15 ms |
35612 KB |
Output is correct |
22 |
Correct |
14 ms |
35472 KB |
Output is correct |
23 |
Correct |
15 ms |
35512 KB |
Output is correct |
24 |
Correct |
16 ms |
35544 KB |
Output is correct |
25 |
Correct |
15 ms |
35556 KB |
Output is correct |
26 |
Correct |
15 ms |
35548 KB |
Output is correct |
27 |
Correct |
17 ms |
36016 KB |
Output is correct |
28 |
Correct |
17 ms |
35924 KB |
Output is correct |
29 |
Correct |
19 ms |
35976 KB |
Output is correct |
30 |
Correct |
15 ms |
35760 KB |
Output is correct |
31 |
Correct |
15 ms |
35792 KB |
Output is correct |
32 |
Correct |
15 ms |
35624 KB |
Output is correct |
33 |
Correct |
16 ms |
35796 KB |
Output is correct |
34 |
Correct |
16 ms |
35696 KB |
Output is correct |
35 |
Correct |
15 ms |
35692 KB |
Output is correct |
36 |
Correct |
16 ms |
36072 KB |
Output is correct |
37 |
Correct |
17 ms |
36052 KB |
Output is correct |
38 |
Correct |
17 ms |
36008 KB |
Output is correct |
39 |
Correct |
16 ms |
36052 KB |
Output is correct |
40 |
Correct |
16 ms |
35796 KB |
Output is correct |
41 |
Correct |
16 ms |
35936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35544 KB |
Output is correct |
2 |
Correct |
16 ms |
35480 KB |
Output is correct |
3 |
Correct |
15 ms |
35452 KB |
Output is correct |
4 |
Correct |
15 ms |
35612 KB |
Output is correct |
5 |
Correct |
15 ms |
35540 KB |
Output is correct |
6 |
Correct |
16 ms |
35548 KB |
Output is correct |
7 |
Correct |
15 ms |
35516 KB |
Output is correct |
8 |
Correct |
19 ms |
35528 KB |
Output is correct |
9 |
Correct |
15 ms |
35552 KB |
Output is correct |
10 |
Correct |
437 ms |
87200 KB |
Output is correct |
11 |
Correct |
482 ms |
97104 KB |
Output is correct |
12 |
Correct |
71 ms |
49752 KB |
Output is correct |
13 |
Correct |
517 ms |
107512 KB |
Output is correct |
14 |
Correct |
152 ms |
93408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
35544 KB |
Output is correct |
2 |
Correct |
16 ms |
35480 KB |
Output is correct |
3 |
Correct |
15 ms |
35452 KB |
Output is correct |
4 |
Correct |
15 ms |
35612 KB |
Output is correct |
5 |
Correct |
15 ms |
35540 KB |
Output is correct |
6 |
Correct |
16 ms |
35548 KB |
Output is correct |
7 |
Correct |
15 ms |
35516 KB |
Output is correct |
8 |
Correct |
19 ms |
35528 KB |
Output is correct |
9 |
Correct |
15 ms |
35552 KB |
Output is correct |
10 |
Correct |
14 ms |
35552 KB |
Output is correct |
11 |
Correct |
15 ms |
35520 KB |
Output is correct |
12 |
Correct |
14 ms |
35540 KB |
Output is correct |
13 |
Correct |
14 ms |
35540 KB |
Output is correct |
14 |
Correct |
15 ms |
35540 KB |
Output is correct |
15 |
Correct |
16 ms |
35560 KB |
Output is correct |
16 |
Correct |
15 ms |
35544 KB |
Output is correct |
17 |
Correct |
19 ms |
35656 KB |
Output is correct |
18 |
Correct |
15 ms |
35540 KB |
Output is correct |
19 |
Correct |
15 ms |
35540 KB |
Output is correct |
20 |
Correct |
15 ms |
35512 KB |
Output is correct |
21 |
Correct |
15 ms |
35612 KB |
Output is correct |
22 |
Correct |
14 ms |
35472 KB |
Output is correct |
23 |
Correct |
15 ms |
35512 KB |
Output is correct |
24 |
Correct |
16 ms |
35544 KB |
Output is correct |
25 |
Correct |
15 ms |
35556 KB |
Output is correct |
26 |
Correct |
15 ms |
35548 KB |
Output is correct |
27 |
Correct |
17 ms |
36016 KB |
Output is correct |
28 |
Correct |
17 ms |
35924 KB |
Output is correct |
29 |
Correct |
19 ms |
35976 KB |
Output is correct |
30 |
Correct |
15 ms |
35760 KB |
Output is correct |
31 |
Correct |
15 ms |
35792 KB |
Output is correct |
32 |
Correct |
15 ms |
35624 KB |
Output is correct |
33 |
Correct |
16 ms |
35796 KB |
Output is correct |
34 |
Correct |
16 ms |
35696 KB |
Output is correct |
35 |
Correct |
15 ms |
35692 KB |
Output is correct |
36 |
Correct |
16 ms |
36072 KB |
Output is correct |
37 |
Correct |
17 ms |
36052 KB |
Output is correct |
38 |
Correct |
17 ms |
36008 KB |
Output is correct |
39 |
Correct |
16 ms |
36052 KB |
Output is correct |
40 |
Correct |
16 ms |
35796 KB |
Output is correct |
41 |
Correct |
16 ms |
35936 KB |
Output is correct |
42 |
Correct |
437 ms |
87200 KB |
Output is correct |
43 |
Correct |
482 ms |
97104 KB |
Output is correct |
44 |
Correct |
71 ms |
49752 KB |
Output is correct |
45 |
Correct |
517 ms |
107512 KB |
Output is correct |
46 |
Correct |
152 ms |
93408 KB |
Output is correct |
47 |
Correct |
14 ms |
35540 KB |
Output is correct |
48 |
Correct |
15 ms |
35548 KB |
Output is correct |
49 |
Correct |
15 ms |
35548 KB |
Output is correct |
50 |
Correct |
158 ms |
84892 KB |
Output is correct |
51 |
Correct |
169 ms |
84492 KB |
Output is correct |
52 |
Correct |
252 ms |
84328 KB |
Output is correct |
53 |
Correct |
226 ms |
84364 KB |
Output is correct |
54 |
Correct |
237 ms |
84372 KB |
Output is correct |
55 |
Correct |
456 ms |
94424 KB |
Output is correct |
56 |
Correct |
295 ms |
105020 KB |
Output is correct |
57 |
Correct |
266 ms |
105760 KB |
Output is correct |
58 |
Correct |
402 ms |
98588 KB |
Output is correct |
59 |
Correct |
646 ms |
108328 KB |
Output is correct |
60 |
Correct |
334 ms |
90696 KB |
Output is correct |
61 |
Correct |
612 ms |
108924 KB |
Output is correct |
62 |
Correct |
913 ms |
197652 KB |
Output is correct |
63 |
Correct |
244 ms |
105516 KB |
Output is correct |
64 |
Correct |
19 ms |
36564 KB |
Output is correct |
65 |
Correct |
17 ms |
36584 KB |
Output is correct |
66 |
Correct |
852 ms |
197660 KB |
Output is correct |
67 |
Correct |
29 ms |
41168 KB |
Output is correct |
68 |
Correct |
40 ms |
44972 KB |
Output is correct |
69 |
Correct |
681 ms |
108504 KB |
Output is correct |
70 |
Correct |
62 ms |
54240 KB |
Output is correct |
71 |
Correct |
171 ms |
93968 KB |
Output is correct |
72 |
Correct |
677 ms |
108324 KB |
Output is correct |
73 |
Correct |
899 ms |
197744 KB |
Output is correct |