# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
435789 |
2021-06-23T17:58:31 Z |
errorgorn |
Keys (IOI21_keys) |
C++17 |
|
2003 ms |
178024 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,m;
int typ[300005];
set<int> keys[300005];
set<ii> al[300005];
vector<int> proc[300005];
int nxt[300005];
struct UFDS{
int p[300005];
int s[300005];
UFDS(){
rep(x,0,300005){
p[x]=x;
s[x]=1;
}
}
int parent(int i){
if (i==p[i]) return i;
else return p[i]=parent(p[i]);
}
void unions(int i,int j){
i=parent(i),j=parent(j);
if (i==j) return;
p[i]=j;
s[j]+=s[i];
}
} roots,connected;
bool vis[300005];
bool onstk[300005];
void dfs(int i){
vis[i]=true;
onstk[i]=true;
if (!vis[nxt[i]]) dfs(nxt[i]);
else if (onstk[nxt[i]]){
//merge root cycle
int curr=nxt[i];
do{
roots.unions(curr,i);
if (sz(keys[i])<sz(keys[curr])) swap(keys[i],keys[curr]);
for (auto &it:keys[curr]) keys[i].insert(it);
if (sz(al[i])<sz(al[curr])) swap(al[i],al[curr]);
for (auto &it:al[curr]) al[i].insert(it);
if (sz(proc[i])<sz(proc[curr])) swap(proc[i],proc[curr]);
for (auto &it:proc[curr]) proc[i].pub(it);
curr=nxt[curr];
} while (curr!=i);
for (auto &it:keys[i]){
while (true){
auto iter=al[i].lb(ii(it,-1));
if (iter!=al[i].end() && (*iter).fi==it){
proc[i].pub((*iter).se);
al[i].erase(iter);
}
else break;
}
}
while (!proc[i].empty()){
int u=proc[i].back(); proc[i].pob();
if (connected.parent(u)!=connected.parent(i)){ //another forest
nxt[i]=u;
connected.unions(i,u);
break;
}
while (roots.parent(u)!=roots.parent(i)){
//if (typ[u]) cout<<"wtf: "<<u<<" "<<typ[u]<<endl;
if (sz(keys[i])+sz(al[i])<sz(keys[u])+sz(al[u])){
swap(keys[i],keys[u]);
swap(al[i],al[u]);
}
for (auto &it:keys[u]){
while (true){
auto iter=al[i].lb(ii(it,-1));
if (iter!=al[i].end() && (*iter).fi==it){
proc[i].pub((*iter).se);
al[i].erase(iter);
}
else break;
}
keys[i].insert(it);
}
for (auto &it:al[u]){
if (keys[i].count(it.fi)){
proc[i].pub(it.se);
}
else{
al[i].insert(it);
}
}
if (sz(proc[i])<sz(proc[u])) swap(proc[i],proc[u]);
for (auto &it:proc[u]) proc[i].pub(it);
roots.unions(u,nxt[u]);
u=roots.parent(u);
}
}
}
onstk[i]=false;
}
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
n=sz(R),m=sz(U);
rep(x,0,n){
typ[x]=R[x];
keys[x].insert(R[x]);
}
rep(x,0,m){
al[U[x]].insert(ii(C[x],V[x]));
al[V[x]].insert(ii(C[x],U[x]));
}
memset(nxt,-1,sizeof(nxt));
rep(x,0,n){
for (auto &it:al[x]) if (it.fi==typ[x]) nxt[x]=it.se;
}
bool trivial=false;
rep(x,0,n) if (nxt[x]==-1) trivial=true;
if (trivial){
vector<int> ans(n,0);
rep(x,0,n) if (nxt[x]==-1) ans[x]=1;
return ans;
}
rep(x,0,n) connected.unions(x,nxt[x]);
//rep(x,0,n) cout<<nxt[x]<<" "; cout<<endl;
rep(x,0,n){
while (true){
auto iter=al[x].lb(ii(typ[x],-1));
if (iter!=al[x].end() && (*iter).fi==typ[x]){
proc[x].pub((*iter).se);
al[x].erase(iter);
}
else break;
}
}
rep(x,0,n) if (!vis[x]) dfs(x);
int best=1e9;
set<int> best_roots;
rep(x,0,n){
if (roots.parent(x)==x && roots.parent(x)==roots.parent(nxt[x])){
if (best>roots.s[x]) best=roots.s[x],best_roots.clear();
if (best==roots.s[x]) best_roots.insert(x);
}
}
//for (auto &it:best_roots) cout<<it<<" "; cout<<endl;
vector<int> ans(n,0);
rep(x,0,n) if (best_roots.count(roots.parent(x))) ans[x]=1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
41292 KB |
Output is correct |
2 |
Correct |
25 ms |
41380 KB |
Output is correct |
3 |
Correct |
25 ms |
41356 KB |
Output is correct |
4 |
Correct |
25 ms |
41448 KB |
Output is correct |
5 |
Correct |
27 ms |
41384 KB |
Output is correct |
6 |
Correct |
26 ms |
41324 KB |
Output is correct |
7 |
Correct |
25 ms |
41400 KB |
Output is correct |
8 |
Correct |
26 ms |
41336 KB |
Output is correct |
9 |
Correct |
25 ms |
41448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
41292 KB |
Output is correct |
2 |
Correct |
25 ms |
41380 KB |
Output is correct |
3 |
Correct |
25 ms |
41356 KB |
Output is correct |
4 |
Correct |
25 ms |
41448 KB |
Output is correct |
5 |
Correct |
27 ms |
41384 KB |
Output is correct |
6 |
Correct |
26 ms |
41324 KB |
Output is correct |
7 |
Correct |
25 ms |
41400 KB |
Output is correct |
8 |
Correct |
26 ms |
41336 KB |
Output is correct |
9 |
Correct |
25 ms |
41448 KB |
Output is correct |
10 |
Correct |
28 ms |
41412 KB |
Output is correct |
11 |
Correct |
28 ms |
41412 KB |
Output is correct |
12 |
Correct |
29 ms |
41448 KB |
Output is correct |
13 |
Correct |
24 ms |
41352 KB |
Output is correct |
14 |
Correct |
24 ms |
41292 KB |
Output is correct |
15 |
Correct |
24 ms |
41464 KB |
Output is correct |
16 |
Correct |
29 ms |
41336 KB |
Output is correct |
17 |
Correct |
27 ms |
41340 KB |
Output is correct |
18 |
Correct |
28 ms |
41408 KB |
Output is correct |
19 |
Correct |
25 ms |
41308 KB |
Output is correct |
20 |
Correct |
24 ms |
41328 KB |
Output is correct |
21 |
Correct |
26 ms |
41468 KB |
Output is correct |
22 |
Correct |
26 ms |
41380 KB |
Output is correct |
23 |
Correct |
24 ms |
41368 KB |
Output is correct |
24 |
Correct |
25 ms |
41408 KB |
Output is correct |
25 |
Correct |
26 ms |
41416 KB |
Output is correct |
26 |
Correct |
25 ms |
41348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
41292 KB |
Output is correct |
2 |
Correct |
25 ms |
41380 KB |
Output is correct |
3 |
Correct |
25 ms |
41356 KB |
Output is correct |
4 |
Correct |
25 ms |
41448 KB |
Output is correct |
5 |
Correct |
27 ms |
41384 KB |
Output is correct |
6 |
Correct |
26 ms |
41324 KB |
Output is correct |
7 |
Correct |
25 ms |
41400 KB |
Output is correct |
8 |
Correct |
26 ms |
41336 KB |
Output is correct |
9 |
Correct |
25 ms |
41448 KB |
Output is correct |
10 |
Correct |
28 ms |
41412 KB |
Output is correct |
11 |
Correct |
28 ms |
41412 KB |
Output is correct |
12 |
Correct |
29 ms |
41448 KB |
Output is correct |
13 |
Correct |
24 ms |
41352 KB |
Output is correct |
14 |
Correct |
24 ms |
41292 KB |
Output is correct |
15 |
Correct |
24 ms |
41464 KB |
Output is correct |
16 |
Correct |
29 ms |
41336 KB |
Output is correct |
17 |
Correct |
27 ms |
41340 KB |
Output is correct |
18 |
Correct |
28 ms |
41408 KB |
Output is correct |
19 |
Correct |
25 ms |
41308 KB |
Output is correct |
20 |
Correct |
24 ms |
41328 KB |
Output is correct |
21 |
Correct |
26 ms |
41468 KB |
Output is correct |
22 |
Correct |
26 ms |
41380 KB |
Output is correct |
23 |
Correct |
24 ms |
41368 KB |
Output is correct |
24 |
Correct |
25 ms |
41408 KB |
Output is correct |
25 |
Correct |
26 ms |
41416 KB |
Output is correct |
26 |
Correct |
25 ms |
41348 KB |
Output is correct |
27 |
Correct |
27 ms |
41800 KB |
Output is correct |
28 |
Correct |
30 ms |
41748 KB |
Output is correct |
29 |
Correct |
26 ms |
41804 KB |
Output is correct |
30 |
Correct |
32 ms |
41676 KB |
Output is correct |
31 |
Correct |
31 ms |
41516 KB |
Output is correct |
32 |
Correct |
27 ms |
41460 KB |
Output is correct |
33 |
Correct |
27 ms |
41592 KB |
Output is correct |
34 |
Correct |
26 ms |
41804 KB |
Output is correct |
35 |
Correct |
29 ms |
41512 KB |
Output is correct |
36 |
Correct |
26 ms |
41788 KB |
Output is correct |
37 |
Correct |
33 ms |
41676 KB |
Output is correct |
38 |
Correct |
26 ms |
41812 KB |
Output is correct |
39 |
Correct |
27 ms |
41704 KB |
Output is correct |
40 |
Correct |
29 ms |
41700 KB |
Output is correct |
41 |
Correct |
29 ms |
41776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
41292 KB |
Output is correct |
2 |
Correct |
25 ms |
41380 KB |
Output is correct |
3 |
Correct |
25 ms |
41356 KB |
Output is correct |
4 |
Correct |
25 ms |
41448 KB |
Output is correct |
5 |
Correct |
27 ms |
41384 KB |
Output is correct |
6 |
Correct |
26 ms |
41324 KB |
Output is correct |
7 |
Correct |
25 ms |
41400 KB |
Output is correct |
8 |
Correct |
26 ms |
41336 KB |
Output is correct |
9 |
Correct |
25 ms |
41448 KB |
Output is correct |
10 |
Correct |
660 ms |
92216 KB |
Output is correct |
11 |
Correct |
1193 ms |
106140 KB |
Output is correct |
12 |
Correct |
169 ms |
54440 KB |
Output is correct |
13 |
Correct |
1006 ms |
104588 KB |
Output is correct |
14 |
Correct |
400 ms |
177840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
41292 KB |
Output is correct |
2 |
Correct |
25 ms |
41380 KB |
Output is correct |
3 |
Correct |
25 ms |
41356 KB |
Output is correct |
4 |
Correct |
25 ms |
41448 KB |
Output is correct |
5 |
Correct |
27 ms |
41384 KB |
Output is correct |
6 |
Correct |
26 ms |
41324 KB |
Output is correct |
7 |
Correct |
25 ms |
41400 KB |
Output is correct |
8 |
Correct |
26 ms |
41336 KB |
Output is correct |
9 |
Correct |
25 ms |
41448 KB |
Output is correct |
10 |
Correct |
28 ms |
41412 KB |
Output is correct |
11 |
Correct |
28 ms |
41412 KB |
Output is correct |
12 |
Correct |
29 ms |
41448 KB |
Output is correct |
13 |
Correct |
24 ms |
41352 KB |
Output is correct |
14 |
Correct |
24 ms |
41292 KB |
Output is correct |
15 |
Correct |
24 ms |
41464 KB |
Output is correct |
16 |
Correct |
29 ms |
41336 KB |
Output is correct |
17 |
Correct |
27 ms |
41340 KB |
Output is correct |
18 |
Correct |
28 ms |
41408 KB |
Output is correct |
19 |
Correct |
25 ms |
41308 KB |
Output is correct |
20 |
Correct |
24 ms |
41328 KB |
Output is correct |
21 |
Correct |
26 ms |
41468 KB |
Output is correct |
22 |
Correct |
26 ms |
41380 KB |
Output is correct |
23 |
Correct |
24 ms |
41368 KB |
Output is correct |
24 |
Correct |
25 ms |
41408 KB |
Output is correct |
25 |
Correct |
26 ms |
41416 KB |
Output is correct |
26 |
Correct |
25 ms |
41348 KB |
Output is correct |
27 |
Correct |
27 ms |
41800 KB |
Output is correct |
28 |
Correct |
30 ms |
41748 KB |
Output is correct |
29 |
Correct |
26 ms |
41804 KB |
Output is correct |
30 |
Correct |
32 ms |
41676 KB |
Output is correct |
31 |
Correct |
31 ms |
41516 KB |
Output is correct |
32 |
Correct |
27 ms |
41460 KB |
Output is correct |
33 |
Correct |
27 ms |
41592 KB |
Output is correct |
34 |
Correct |
26 ms |
41804 KB |
Output is correct |
35 |
Correct |
29 ms |
41512 KB |
Output is correct |
36 |
Correct |
26 ms |
41788 KB |
Output is correct |
37 |
Correct |
33 ms |
41676 KB |
Output is correct |
38 |
Correct |
26 ms |
41812 KB |
Output is correct |
39 |
Correct |
27 ms |
41704 KB |
Output is correct |
40 |
Correct |
29 ms |
41700 KB |
Output is correct |
41 |
Correct |
29 ms |
41776 KB |
Output is correct |
42 |
Correct |
660 ms |
92216 KB |
Output is correct |
43 |
Correct |
1193 ms |
106140 KB |
Output is correct |
44 |
Correct |
169 ms |
54440 KB |
Output is correct |
45 |
Correct |
1006 ms |
104588 KB |
Output is correct |
46 |
Correct |
400 ms |
177840 KB |
Output is correct |
47 |
Correct |
28 ms |
41408 KB |
Output is correct |
48 |
Correct |
28 ms |
41384 KB |
Output is correct |
49 |
Correct |
27 ms |
41376 KB |
Output is correct |
50 |
Correct |
365 ms |
137716 KB |
Output is correct |
51 |
Correct |
269 ms |
104772 KB |
Output is correct |
52 |
Correct |
401 ms |
83676 KB |
Output is correct |
53 |
Correct |
399 ms |
83808 KB |
Output is correct |
54 |
Correct |
374 ms |
83664 KB |
Output is correct |
55 |
Correct |
606 ms |
92248 KB |
Output is correct |
56 |
Correct |
663 ms |
104732 KB |
Output is correct |
57 |
Correct |
765 ms |
104928 KB |
Output is correct |
58 |
Correct |
796 ms |
104880 KB |
Output is correct |
59 |
Correct |
1844 ms |
145892 KB |
Output is correct |
60 |
Correct |
560 ms |
98520 KB |
Output is correct |
61 |
Correct |
601 ms |
98476 KB |
Output is correct |
62 |
Correct |
590 ms |
94192 KB |
Output is correct |
63 |
Correct |
419 ms |
100684 KB |
Output is correct |
64 |
Correct |
34 ms |
43716 KB |
Output is correct |
65 |
Correct |
32 ms |
43744 KB |
Output is correct |
66 |
Correct |
582 ms |
94172 KB |
Output is correct |
67 |
Correct |
63 ms |
55020 KB |
Output is correct |
68 |
Correct |
80 ms |
64048 KB |
Output is correct |
69 |
Correct |
1818 ms |
132528 KB |
Output is correct |
70 |
Correct |
135 ms |
86656 KB |
Output is correct |
71 |
Correct |
400 ms |
178024 KB |
Output is correct |
72 |
Correct |
2003 ms |
145936 KB |
Output is correct |
73 |
Correct |
572 ms |
94148 KB |
Output is correct |