# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
445077 |
2021-07-16T11:12:48 Z |
hhhhaura |
Keys (IOI21_keys) |
C++17 |
|
1407 ms |
140844 KB |
#include <vector>
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define INF 1000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#define ll long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() {cerr << endl;}
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
int ii;
vector<vector<pii>> mp;
vector<int> R, instack;
set<int> avail;
namespace dsu {
int n;
vector<int> sz, par;
vector<set<int>> col;
vector<set<pii>> good, bad;
void init_(int _n) {
n = _n;
sz.assign(n + 1, 1);
par.assign(n + 1, 0);
col.assign(n + 1, set<int>());
good.assign(n + 1, set<pii>());
bad.assign(n + 1, set<pii>());
rep(i, 0, n - 1) {
par[i] = i;
col[i].insert(R[i]);
for(auto j : mp[i]) {
if(j.first == R[i]) good[i].insert(j);
else bad[i].insert(j);
}
}
}
int find_par(int a) {
while(a != par[a]) a = par[a];
return par[a];
}
bool same(int a, int b) {
return find_par(a) == find_par(b);
}
void unite(int a, int b) {
int aa = find_par(a);
int bb = find_par(b);
if(aa == bb) return;
if(sz[aa] < sz[bb]) swap(aa, bb);
sz[aa] += sz[bb], par[bb] = aa;
if(good[aa].size() < good[bb].size()) {
for(auto i : good[aa]) good[bb].insert(i);
good[aa].swap(good[bb]);
}
else for(auto i : good[bb]) good[aa].insert(i);
good[bb].clear();
for(auto i : col[bb]) {
col[aa].insert(i);
auto it = bad[aa].lower_bound(pii(i, -INF));
while(it != bad[aa].end() && it->first == i ) {
good[aa].insert({it->first, it->second});
auto temp = it; it = next(it);
bad[aa].erase(temp);
}
}
// wrong
col[bb].clear();
for(auto i : bad[bb]) {
if(col[aa].find(i.first) != col[aa].end()) {
good[aa].insert(i);
}
else bad[aa].insert(i);
}
bad[bb].clear();
}
};
int get(int x) { return dsu::find_par(x); }
void operate(int x) {
stack<int> st;
st.push(x);
instack[x] = ii;
bool ok = 1;
while(dsu::good[get(st.top())].size()) {
int p = get(st.top());
pii cur = *dsu::good[p].begin();
dsu::good[p].erase(dsu::good[p].find(cur));
if(dsu::same(cur.second, p)) continue;
cur.second = get(cur.second);
if(instack[cur.second] && instack[cur.second] != ii) {
ok = 0;
break;
}
else if(instack[cur.second]) {
while(get(st.top()) != get(cur.second)) {
int k = st.top(); st.pop();
dsu::unite(k, cur.second);
}
}
else {
instack[cur.second] = ii;
st.push(cur.second);
}
}
if(ok) avail.insert(get(st.top()));
return;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
vector<int> ans(r.size(), 0);
int n = r.size();
R = r, ii = 0;
mp.assign(n, vector<pii>());
instack.assign(n, 0);
rep(i, 0, signed(u.size()) - 1) {
mp[u[i]].push_back({c[i], v[i]});
mp[v[i]].push_back({c[i], u[i]});
}
dsu::init_(n);
rep(i, 0, n - 1) {
if(!instack[i]) ii ++, operate(i);
}
int mn = INF;
rep(i, 0, n - 1) if(avail.find(get(i)) != avail.end()) {
mn = min(mn, dsu::sz[get(i)]);
}
rep(i, 0, n - 1) if(avail.find(get(i)) != avail.end()) {
if(dsu::sz[get(i)] == mn) ans[i] = 1;
}
return ans;
}
Compilation message
keys.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
5 | #pragma loop-opt(on)
|
keys.cpp:25:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
25 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
keys.cpp:25:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
25 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
224 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
224 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
292 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
296 KB |
Output is correct |
22 |
Correct |
1 ms |
204 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 |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
224 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
292 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
296 KB |
Output is correct |
22 |
Correct |
1 ms |
204 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 |
3 ms |
1100 KB |
Output is correct |
28 |
Correct |
3 ms |
1100 KB |
Output is correct |
29 |
Correct |
3 ms |
1228 KB |
Output is correct |
30 |
Correct |
2 ms |
588 KB |
Output is correct |
31 |
Correct |
2 ms |
716 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
2 ms |
588 KB |
Output is correct |
34 |
Correct |
2 ms |
684 KB |
Output is correct |
35 |
Correct |
2 ms |
588 KB |
Output is correct |
36 |
Correct |
2 ms |
972 KB |
Output is correct |
37 |
Correct |
4 ms |
972 KB |
Output is correct |
38 |
Correct |
4 ms |
1000 KB |
Output is correct |
39 |
Correct |
4 ms |
1072 KB |
Output is correct |
40 |
Correct |
2 ms |
716 KB |
Output is correct |
41 |
Correct |
3 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
224 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
532 ms |
72156 KB |
Output is correct |
11 |
Correct |
863 ms |
136792 KB |
Output is correct |
12 |
Correct |
116 ms |
22340 KB |
Output is correct |
13 |
Correct |
1028 ms |
112008 KB |
Output is correct |
14 |
Correct |
293 ms |
121932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
224 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
292 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
296 KB |
Output is correct |
22 |
Correct |
1 ms |
204 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 |
3 ms |
1100 KB |
Output is correct |
28 |
Correct |
3 ms |
1100 KB |
Output is correct |
29 |
Correct |
3 ms |
1228 KB |
Output is correct |
30 |
Correct |
2 ms |
588 KB |
Output is correct |
31 |
Correct |
2 ms |
716 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
2 ms |
588 KB |
Output is correct |
34 |
Correct |
2 ms |
684 KB |
Output is correct |
35 |
Correct |
2 ms |
588 KB |
Output is correct |
36 |
Correct |
2 ms |
972 KB |
Output is correct |
37 |
Correct |
4 ms |
972 KB |
Output is correct |
38 |
Correct |
4 ms |
1000 KB |
Output is correct |
39 |
Correct |
4 ms |
1072 KB |
Output is correct |
40 |
Correct |
2 ms |
716 KB |
Output is correct |
41 |
Correct |
3 ms |
844 KB |
Output is correct |
42 |
Correct |
532 ms |
72156 KB |
Output is correct |
43 |
Correct |
863 ms |
136792 KB |
Output is correct |
44 |
Correct |
116 ms |
22340 KB |
Output is correct |
45 |
Correct |
1028 ms |
112008 KB |
Output is correct |
46 |
Correct |
293 ms |
121932 KB |
Output is correct |
47 |
Correct |
1 ms |
204 KB |
Output is correct |
48 |
Correct |
1 ms |
204 KB |
Output is correct |
49 |
Correct |
1 ms |
204 KB |
Output is correct |
50 |
Correct |
321 ms |
122072 KB |
Output is correct |
51 |
Correct |
359 ms |
124856 KB |
Output is correct |
52 |
Correct |
410 ms |
86468 KB |
Output is correct |
53 |
Correct |
427 ms |
86488 KB |
Output is correct |
54 |
Correct |
380 ms |
86236 KB |
Output is correct |
55 |
Correct |
660 ms |
73572 KB |
Output is correct |
56 |
Correct |
658 ms |
130616 KB |
Output is correct |
57 |
Correct |
800 ms |
140844 KB |
Output is correct |
58 |
Correct |
680 ms |
126820 KB |
Output is correct |
59 |
Correct |
1310 ms |
100496 KB |
Output is correct |
60 |
Correct |
1204 ms |
100684 KB |
Output is correct |
61 |
Correct |
1407 ms |
100960 KB |
Output is correct |
62 |
Correct |
1116 ms |
81692 KB |
Output is correct |
63 |
Correct |
354 ms |
89800 KB |
Output is correct |
64 |
Correct |
6 ms |
2252 KB |
Output is correct |
65 |
Correct |
6 ms |
2252 KB |
Output is correct |
66 |
Correct |
1082 ms |
81760 KB |
Output is correct |
67 |
Correct |
31 ms |
12484 KB |
Output is correct |
68 |
Correct |
53 ms |
20532 KB |
Output is correct |
69 |
Correct |
1345 ms |
100204 KB |
Output is correct |
70 |
Correct |
101 ms |
40900 KB |
Output is correct |
71 |
Correct |
309 ms |
122480 KB |
Output is correct |
72 |
Correct |
1297 ms |
100460 KB |
Output is correct |
73 |
Correct |
1047 ms |
81700 KB |
Output is correct |