# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
484527 |
2021-11-04T04:33:27 Z |
wwdd |
Keys (IOI21_keys) |
C++17 |
|
1196 ms |
129440 KB |
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
class U {
private:
vi p,rk;
int n;
public:
U(int sz) {
n = sz;
for(int i=0;i<n;i++) {
p.push_back(i);
}
rk.assign(n,0);
}
int find(int a) {
if(p[a] == a) {
return a;
}
return p[a] = find(p[a]);
}
inline bool same(int a, int b) {
return find(a) == find(b);
}
int un(int a, int b) {
if(same(a,b)) {return -1;}
int x = find(a);
int y = find(b);
if(rk[x] < rk[y]) {swap(x,y);}
if(rk[x] == rk[y]) {rk[x]++;}
p[y] = x;
return x;
}
};
struct NO {
map<int,list<int>> eg;
set<int> cols;
list<int> act,reps;
int sz;
NO(int u) {
sz = 1;
reps.push_back(u);
}
void morg(NO& ot) {
reps.splice(reps.end(),ot.reps);
sz += ot.sz;
ot.sz = -1;
if(cols.size()+eg.size() < ot.cols.size()+ot.eg.size()) {
swap(cols,ot.cols);
swap(eg,ot.eg);
}
for(const auto& col: ot.cols) {
if(eg.count(col)) {
act.splice(act.end(),eg[col]);
eg.erase(col);
}
}
cols.insert(ot.cols.begin(),ot.cols.end());
ot.cols.clear();
for(auto& ek: ot.eg) {
if(cols.count(ek.first)) {
act.splice(act.end(),ek.second);
} else {
list<int>& cur = eg[ek.first];
if(ek.second.size() > cur.size()) {
swap(cur,ek.second);
}
cur.splice(cur.end(),ek.second);
}
ek.second.clear();
}
ot.eg.clear();
act.splice(act.end(),ot.act);
}
};
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
vector<NO> wu;
for(int i=0;i<r.size();i++) {
wu.emplace_back(i);
wu[i].cols.insert(r[i]);
}
for(int i=0;i<u.size();i++) {
int vu = u[i];
int vv = v[i];
int vc = c[i];
if(vc == r[vu]) {
wu[vu].act.push_back(vv);
} else {
wu[vu].eg[vc].push_back(vv);
}
if(vc == r[vv]) {
wu[vv].act.push_back(vu);
} else {
wu[vv].eg[vc].push_back(vu);
}
}
vi st;
U bu(r.size());
vector<bool> wac(r.size());
vi vs(r.size());
vi enb;
for(int sti=0;sti<r.size();sti++) {
if(vs[sti]) {continue;}
vs[sti] = 1;
st.push_back(sti);wac[sti] = 1;
bool cont = true;
int los;
while(cont) {
int vu = st.back();
int nx = -1;
while(!wu[vu].act.empty()) {
int nu = wu[vu].act.back();
nu = bu.find(nu);
wu[vu].act.pop_back();
if(nu == vu) {continue;}
if(wac[nu]) {
st.pop_back();wac[vu] = 0;
while(!bu.same(nu,vu)) {
int vv = st.back();st.pop_back();wac[vv] = 0;
int com = bu.un(vv,vu);
wu[com].morg(wu[vv+vu-com]);
vu = com;
}
st.push_back(vu);wac[vu] = 1;
} else if(vs[nu]) {
cont = false;break;
} else {
nx = nu;break;
}
}
if(nx == -1) {
los = vu;
break;
} else {
vs[nx] = 1;
st.push_back(nx);
wac[nx] = true;
}
}
while(!st.empty()) {
wac[st.back()] = false;
st.pop_back();
}
if(cont) {
enb.push_back(los);
}
}
int ma = r.size()+1;
for(const auto& mat: enb) {
ma = min(ma,wu[mat].sz);
}
std::vector<int> ans(r.size(), 0);
for(const auto& mat: enb) {
if(wu[mat].sz == ma) {
for(const auto& it: wu[mat].reps) {
ans[it] = 1;
}
}
}
return ans;
}
Compilation message
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:85:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=0;i<r.size();i++) {
| ~^~~~~~~~~
keys.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int i=0;i<u.size();i++) {
| ~^~~~~~~~~
keys.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int sti=0;sti<r.size();sti++) {
| ~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
288 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
288 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
1200 KB |
Output is correct |
28 |
Correct |
2 ms |
1200 KB |
Output is correct |
29 |
Correct |
2 ms |
1200 KB |
Output is correct |
30 |
Correct |
2 ms |
588 KB |
Output is correct |
31 |
Correct |
1 ms |
716 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
588 KB |
Output is correct |
34 |
Correct |
1 ms |
588 KB |
Output is correct |
35 |
Correct |
1 ms |
588 KB |
Output is correct |
36 |
Correct |
3 ms |
1048 KB |
Output is correct |
37 |
Correct |
2 ms |
1048 KB |
Output is correct |
38 |
Correct |
3 ms |
1072 KB |
Output is correct |
39 |
Correct |
2 ms |
1100 KB |
Output is correct |
40 |
Correct |
1 ms |
716 KB |
Output is correct |
41 |
Correct |
3 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
575 ms |
85084 KB |
Output is correct |
11 |
Correct |
472 ms |
110364 KB |
Output is correct |
12 |
Correct |
87 ms |
24244 KB |
Output is correct |
13 |
Correct |
528 ms |
117468 KB |
Output is correct |
14 |
Correct |
248 ms |
110444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
288 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
1200 KB |
Output is correct |
28 |
Correct |
2 ms |
1200 KB |
Output is correct |
29 |
Correct |
2 ms |
1200 KB |
Output is correct |
30 |
Correct |
2 ms |
588 KB |
Output is correct |
31 |
Correct |
1 ms |
716 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
588 KB |
Output is correct |
34 |
Correct |
1 ms |
588 KB |
Output is correct |
35 |
Correct |
1 ms |
588 KB |
Output is correct |
36 |
Correct |
3 ms |
1048 KB |
Output is correct |
37 |
Correct |
2 ms |
1048 KB |
Output is correct |
38 |
Correct |
3 ms |
1072 KB |
Output is correct |
39 |
Correct |
2 ms |
1100 KB |
Output is correct |
40 |
Correct |
1 ms |
716 KB |
Output is correct |
41 |
Correct |
3 ms |
844 KB |
Output is correct |
42 |
Correct |
575 ms |
85084 KB |
Output is correct |
43 |
Correct |
472 ms |
110364 KB |
Output is correct |
44 |
Correct |
87 ms |
24244 KB |
Output is correct |
45 |
Correct |
528 ms |
117468 KB |
Output is correct |
46 |
Correct |
248 ms |
110444 KB |
Output is correct |
47 |
Correct |
0 ms |
204 KB |
Output is correct |
48 |
Correct |
1 ms |
204 KB |
Output is correct |
49 |
Correct |
0 ms |
204 KB |
Output is correct |
50 |
Correct |
236 ms |
110420 KB |
Output is correct |
51 |
Correct |
254 ms |
110448 KB |
Output is correct |
52 |
Correct |
383 ms |
94320 KB |
Output is correct |
53 |
Correct |
377 ms |
94340 KB |
Output is correct |
54 |
Correct |
389 ms |
94464 KB |
Output is correct |
55 |
Correct |
724 ms |
92444 KB |
Output is correct |
56 |
Correct |
516 ms |
129100 KB |
Output is correct |
57 |
Correct |
428 ms |
129440 KB |
Output is correct |
58 |
Correct |
649 ms |
127904 KB |
Output is correct |
59 |
Correct |
1196 ms |
110792 KB |
Output is correct |
60 |
Correct |
511 ms |
105048 KB |
Output is correct |
61 |
Correct |
827 ms |
105124 KB |
Output is correct |
62 |
Correct |
777 ms |
91768 KB |
Output is correct |
63 |
Correct |
250 ms |
97028 KB |
Output is correct |
64 |
Correct |
4 ms |
2072 KB |
Output is correct |
65 |
Correct |
5 ms |
2072 KB |
Output is correct |
66 |
Correct |
809 ms |
91904 KB |
Output is correct |
67 |
Correct |
23 ms |
10984 KB |
Output is correct |
68 |
Correct |
41 ms |
18372 KB |
Output is correct |
69 |
Correct |
1167 ms |
111048 KB |
Output is correct |
70 |
Correct |
81 ms |
36344 KB |
Output is correct |
71 |
Correct |
255 ms |
110324 KB |
Output is correct |
72 |
Correct |
1167 ms |
110916 KB |
Output is correct |
73 |
Correct |
800 ms |
91848 KB |
Output is correct |