# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
559494 |
2022-05-10T04:31:21 Z |
8e7 |
Keys (IOI21_keys) |
C++17 |
|
1046 ms |
351304 KB |
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define pii pair<int, int>
#define ff first
#define ss second
unordered_set<int> se[maxn];
unordered_map<int, vector<int> > adj[maxn];
//vector<pii> adj[maxn];
queue<int> to[maxn];
int par[maxn];
bool vis[maxn], stop[maxn], done[maxn];
int ed[maxn], siz[maxn], as[maxn];
void ini(int n) {
for (int i = 0;i < n;i++) par[i] = i;
}
int find(int n) {
return par[n] == n ? n : (par[n] = find(par[n]));
}
void Union(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
debug("merge", a, b);
if (se[a].size() + as[a] + to[a].size() < se[b].size() + as[b] + to[b].size()) swap(a, b);
//a <-- b
for (auto x:adj[b]) {
int c = x.ff;
if (se[a].find(c) != se[a].end()) {
for (int v:x.ss) to[a].push(v);
} else {
adj[a][c].insert(adj[a][c].end(), x.ss.begin(), x.ss.end());
as[a] += x.ss.size();
}
}
adj[b].clear();
for (auto c:se[b]) {
if (adj[a].find(c) != adj[a].end()) {
for (int v:adj[a][c]) to[a].push(v);
as[a] -= adj[a][c].size();
adj[a].erase(c);
}
se[a].insert(c);
}
while (to[b].size()) {
to[a].push(to[b].front()); to[b].pop();
}
par[b] = a;
}
void walk(int st) {
vector<int> path;
int cur = find(st);
while (true) {
debug(cur, to[cur].size());
cur = find(cur);
vis[cur] = 1;
path.push_back(cur);
while (to[cur].size() && find(to[cur].front()) == cur) to[cur].pop();
if (to[cur].size() == 0) {
stop[cur] = 1;
break;
} else {
int nxt = find(to[cur].front());to[cur].pop();
debug(cur, nxt, done[nxt], vis[nxt]);
if (done[nxt]) {
break;
} else if (vis[nxt]) {
int tmp = find(ed[nxt]);
while (nxt != cur) {
Union(nxt, tmp);
nxt = tmp;
tmp = find(ed[nxt]);
}
} else {
ed[cur] = nxt;
cur = nxt;
}
}
}
for (int i:path) done[find(i)] = 1;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size(), m = u.size();
ini(n);
for (int i = 0;i < n;i++) {
se[i].insert(r[i]);
}
for (int i = 0;i < m;i++) {
if (r[u[i]] == c[i]) {
to[u[i]].push(v[i]);
} else {
adj[u[i]][c[i]].push_back(v[i]);
as[u[i]]++;
}
if (r[v[i]] == c[i]) {
to[v[i]].push(u[i]);
} else {
adj[v[i]][c[i]].push_back(u[i]);
as[v[i]]++;
}
}
for (int i = 0;i < n;i++) {
if (!done[find(i)]) {
debug("walk", i);
walk(i);
}
}
for (int i = 0;i < n;i++) siz[find(i)]++;
int mi = 1<<30;
pary(stop, stop + n);
for (int i = 0;i < n;i++) {
if (stop[i]) {
mi = min(mi, siz[i]);
}
}
vector<int> ans(n, 0);
for (int i = 0;i < n;i++) {
if (siz[find(i)] == mi && stop[find(i)]) ans[i] = 1;
}
return ans;
}
Compilation message
keys.cpp: In function 'void Union(int, int)':
keys.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
keys.cpp:39:2: note: in expansion of macro 'debug'
39 | debug("merge", a, b);
| ^~~~~
keys.cpp: In function 'void walk(int)':
keys.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
keys.cpp:69:3: note: in expansion of macro 'debug'
69 | debug(cur, to[cur].size());
| ^~~~~
keys.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
keys.cpp:79:4: note: in expansion of macro 'debug'
79 | debug(cur, nxt, done[nxt], vis[nxt]);
| ^~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
keys.cpp:120:4: note: in expansion of macro 'debug'
120 | debug("walk", i);
| ^~~~~
keys.cpp:13:19: warning: statement has no effect [-Wunused-value]
13 | #define pary(...) 0
| ^
keys.cpp:126:2: note: in expansion of macro 'pary'
126 | pary(stop, stop + n);
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
235104 KB |
Output is correct |
2 |
Correct |
136 ms |
235160 KB |
Output is correct |
3 |
Correct |
135 ms |
235116 KB |
Output is correct |
4 |
Correct |
135 ms |
235092 KB |
Output is correct |
5 |
Correct |
133 ms |
235080 KB |
Output is correct |
6 |
Correct |
136 ms |
235108 KB |
Output is correct |
7 |
Correct |
134 ms |
235068 KB |
Output is correct |
8 |
Correct |
134 ms |
235184 KB |
Output is correct |
9 |
Correct |
136 ms |
235120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
235104 KB |
Output is correct |
2 |
Correct |
136 ms |
235160 KB |
Output is correct |
3 |
Correct |
135 ms |
235116 KB |
Output is correct |
4 |
Correct |
135 ms |
235092 KB |
Output is correct |
5 |
Correct |
133 ms |
235080 KB |
Output is correct |
6 |
Correct |
136 ms |
235108 KB |
Output is correct |
7 |
Correct |
134 ms |
235068 KB |
Output is correct |
8 |
Correct |
134 ms |
235184 KB |
Output is correct |
9 |
Correct |
136 ms |
235120 KB |
Output is correct |
10 |
Correct |
137 ms |
235236 KB |
Output is correct |
11 |
Correct |
141 ms |
235116 KB |
Output is correct |
12 |
Correct |
134 ms |
235232 KB |
Output is correct |
13 |
Correct |
136 ms |
235164 KB |
Output is correct |
14 |
Correct |
135 ms |
235160 KB |
Output is correct |
15 |
Correct |
134 ms |
235212 KB |
Output is correct |
16 |
Correct |
137 ms |
235116 KB |
Output is correct |
17 |
Correct |
147 ms |
235152 KB |
Output is correct |
18 |
Correct |
135 ms |
235276 KB |
Output is correct |
19 |
Correct |
142 ms |
235160 KB |
Output is correct |
20 |
Correct |
138 ms |
235188 KB |
Output is correct |
21 |
Correct |
135 ms |
235212 KB |
Output is correct |
22 |
Correct |
135 ms |
235192 KB |
Output is correct |
23 |
Correct |
135 ms |
235312 KB |
Output is correct |
24 |
Correct |
139 ms |
235212 KB |
Output is correct |
25 |
Correct |
137 ms |
235212 KB |
Output is correct |
26 |
Correct |
135 ms |
235144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
235104 KB |
Output is correct |
2 |
Correct |
136 ms |
235160 KB |
Output is correct |
3 |
Correct |
135 ms |
235116 KB |
Output is correct |
4 |
Correct |
135 ms |
235092 KB |
Output is correct |
5 |
Correct |
133 ms |
235080 KB |
Output is correct |
6 |
Correct |
136 ms |
235108 KB |
Output is correct |
7 |
Correct |
134 ms |
235068 KB |
Output is correct |
8 |
Correct |
134 ms |
235184 KB |
Output is correct |
9 |
Correct |
136 ms |
235120 KB |
Output is correct |
10 |
Correct |
137 ms |
235236 KB |
Output is correct |
11 |
Correct |
141 ms |
235116 KB |
Output is correct |
12 |
Correct |
134 ms |
235232 KB |
Output is correct |
13 |
Correct |
136 ms |
235164 KB |
Output is correct |
14 |
Correct |
135 ms |
235160 KB |
Output is correct |
15 |
Correct |
134 ms |
235212 KB |
Output is correct |
16 |
Correct |
137 ms |
235116 KB |
Output is correct |
17 |
Correct |
147 ms |
235152 KB |
Output is correct |
18 |
Correct |
135 ms |
235276 KB |
Output is correct |
19 |
Correct |
142 ms |
235160 KB |
Output is correct |
20 |
Correct |
138 ms |
235188 KB |
Output is correct |
21 |
Correct |
135 ms |
235212 KB |
Output is correct |
22 |
Correct |
135 ms |
235192 KB |
Output is correct |
23 |
Correct |
135 ms |
235312 KB |
Output is correct |
24 |
Correct |
139 ms |
235212 KB |
Output is correct |
25 |
Correct |
137 ms |
235212 KB |
Output is correct |
26 |
Correct |
135 ms |
235144 KB |
Output is correct |
27 |
Correct |
139 ms |
235908 KB |
Output is correct |
28 |
Correct |
137 ms |
236016 KB |
Output is correct |
29 |
Correct |
140 ms |
235984 KB |
Output is correct |
30 |
Correct |
151 ms |
235476 KB |
Output is correct |
31 |
Correct |
135 ms |
235536 KB |
Output is correct |
32 |
Correct |
136 ms |
235212 KB |
Output is correct |
33 |
Correct |
136 ms |
235380 KB |
Output is correct |
34 |
Correct |
148 ms |
235504 KB |
Output is correct |
35 |
Correct |
153 ms |
235600 KB |
Output is correct |
36 |
Correct |
138 ms |
235708 KB |
Output is correct |
37 |
Correct |
142 ms |
235820 KB |
Output is correct |
38 |
Correct |
137 ms |
235880 KB |
Output is correct |
39 |
Correct |
151 ms |
235888 KB |
Output is correct |
40 |
Correct |
136 ms |
235568 KB |
Output is correct |
41 |
Correct |
149 ms |
235700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
235104 KB |
Output is correct |
2 |
Correct |
136 ms |
235160 KB |
Output is correct |
3 |
Correct |
135 ms |
235116 KB |
Output is correct |
4 |
Correct |
135 ms |
235092 KB |
Output is correct |
5 |
Correct |
133 ms |
235080 KB |
Output is correct |
6 |
Correct |
136 ms |
235108 KB |
Output is correct |
7 |
Correct |
134 ms |
235068 KB |
Output is correct |
8 |
Correct |
134 ms |
235184 KB |
Output is correct |
9 |
Correct |
136 ms |
235120 KB |
Output is correct |
10 |
Correct |
680 ms |
302196 KB |
Output is correct |
11 |
Correct |
480 ms |
293264 KB |
Output is correct |
12 |
Correct |
243 ms |
256012 KB |
Output is correct |
13 |
Correct |
765 ms |
338812 KB |
Output is correct |
14 |
Correct |
346 ms |
293212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
235104 KB |
Output is correct |
2 |
Correct |
136 ms |
235160 KB |
Output is correct |
3 |
Correct |
135 ms |
235116 KB |
Output is correct |
4 |
Correct |
135 ms |
235092 KB |
Output is correct |
5 |
Correct |
133 ms |
235080 KB |
Output is correct |
6 |
Correct |
136 ms |
235108 KB |
Output is correct |
7 |
Correct |
134 ms |
235068 KB |
Output is correct |
8 |
Correct |
134 ms |
235184 KB |
Output is correct |
9 |
Correct |
136 ms |
235120 KB |
Output is correct |
10 |
Correct |
137 ms |
235236 KB |
Output is correct |
11 |
Correct |
141 ms |
235116 KB |
Output is correct |
12 |
Correct |
134 ms |
235232 KB |
Output is correct |
13 |
Correct |
136 ms |
235164 KB |
Output is correct |
14 |
Correct |
135 ms |
235160 KB |
Output is correct |
15 |
Correct |
134 ms |
235212 KB |
Output is correct |
16 |
Correct |
137 ms |
235116 KB |
Output is correct |
17 |
Correct |
147 ms |
235152 KB |
Output is correct |
18 |
Correct |
135 ms |
235276 KB |
Output is correct |
19 |
Correct |
142 ms |
235160 KB |
Output is correct |
20 |
Correct |
138 ms |
235188 KB |
Output is correct |
21 |
Correct |
135 ms |
235212 KB |
Output is correct |
22 |
Correct |
135 ms |
235192 KB |
Output is correct |
23 |
Correct |
135 ms |
235312 KB |
Output is correct |
24 |
Correct |
139 ms |
235212 KB |
Output is correct |
25 |
Correct |
137 ms |
235212 KB |
Output is correct |
26 |
Correct |
135 ms |
235144 KB |
Output is correct |
27 |
Correct |
139 ms |
235908 KB |
Output is correct |
28 |
Correct |
137 ms |
236016 KB |
Output is correct |
29 |
Correct |
140 ms |
235984 KB |
Output is correct |
30 |
Correct |
151 ms |
235476 KB |
Output is correct |
31 |
Correct |
135 ms |
235536 KB |
Output is correct |
32 |
Correct |
136 ms |
235212 KB |
Output is correct |
33 |
Correct |
136 ms |
235380 KB |
Output is correct |
34 |
Correct |
148 ms |
235504 KB |
Output is correct |
35 |
Correct |
153 ms |
235600 KB |
Output is correct |
36 |
Correct |
138 ms |
235708 KB |
Output is correct |
37 |
Correct |
142 ms |
235820 KB |
Output is correct |
38 |
Correct |
137 ms |
235880 KB |
Output is correct |
39 |
Correct |
151 ms |
235888 KB |
Output is correct |
40 |
Correct |
136 ms |
235568 KB |
Output is correct |
41 |
Correct |
149 ms |
235700 KB |
Output is correct |
42 |
Correct |
680 ms |
302196 KB |
Output is correct |
43 |
Correct |
480 ms |
293264 KB |
Output is correct |
44 |
Correct |
243 ms |
256012 KB |
Output is correct |
45 |
Correct |
765 ms |
338812 KB |
Output is correct |
46 |
Correct |
346 ms |
293212 KB |
Output is correct |
47 |
Correct |
140 ms |
235168 KB |
Output is correct |
48 |
Correct |
141 ms |
235116 KB |
Output is correct |
49 |
Correct |
136 ms |
235272 KB |
Output is correct |
50 |
Correct |
361 ms |
294400 KB |
Output is correct |
51 |
Correct |
365 ms |
292596 KB |
Output is correct |
52 |
Correct |
459 ms |
319948 KB |
Output is correct |
53 |
Correct |
446 ms |
320028 KB |
Output is correct |
54 |
Correct |
445 ms |
320076 KB |
Output is correct |
55 |
Correct |
697 ms |
309384 KB |
Output is correct |
56 |
Correct |
558 ms |
351304 KB |
Output is correct |
57 |
Correct |
491 ms |
350484 KB |
Output is correct |
58 |
Correct |
453 ms |
317716 KB |
Output is correct |
59 |
Correct |
949 ms |
322432 KB |
Output is correct |
60 |
Correct |
871 ms |
329316 KB |
Output is correct |
61 |
Correct |
884 ms |
329196 KB |
Output is correct |
62 |
Correct |
1027 ms |
330312 KB |
Output is correct |
63 |
Correct |
442 ms |
317004 KB |
Output is correct |
64 |
Correct |
156 ms |
236368 KB |
Output is correct |
65 |
Correct |
154 ms |
236284 KB |
Output is correct |
66 |
Correct |
1046 ms |
330044 KB |
Output is correct |
67 |
Correct |
170 ms |
241616 KB |
Output is correct |
68 |
Correct |
182 ms |
245396 KB |
Output is correct |
69 |
Correct |
956 ms |
322524 KB |
Output is correct |
70 |
Correct |
235 ms |
255212 KB |
Output is correct |
71 |
Correct |
366 ms |
295184 KB |
Output is correct |
72 |
Correct |
943 ms |
322568 KB |
Output is correct |
73 |
Correct |
1026 ms |
330152 KB |
Output is correct |