# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
702102 |
2023-02-22T21:21:51 Z |
Lobo |
Keys (IOI21_keys) |
C++17 |
|
2710 ms |
185056 KB |
#include<bits/stdc++.h>
using namespace std;
const long long inf = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 3e5+10;
int n, m, ds[maxn], dsz[maxn], mark[maxn], nx[maxn];
unordered_set<int> keys[maxn];
vector<int> edgatv[maxn];
unordered_map<int,vector<int>> edgblk[maxn];
queue<int> q;
int find(int v) {
if(v == ds[v]) return v;
return ds[v] = find(ds[v]);
}
void join(int u, int v) {
if(dsz[u] < dsz[v]) swap(u,v);
for(auto k : keys[v]) {
if(edgblk[u].count(k)) {
for(auto x : edgblk[u][k]) {
edgatv[u].pb(x);
}
edgblk[u].erase(k);
}
keys[u].insert(k);
}
for(auto X : edgblk[v]) {
int c = X.fr;
if(keys[u].count(c)) {
for(auto x : edgblk[v][c]) {
edgatv[u].pb(x);
}
}
else {
for(auto x : edgblk[v][c]) {
edgblk[u][c].pb(x);
}
}
}
for(auto x : edgatv[v]) {
edgatv[u].pb(x);
}
ds[v] = u;
dsz[u]+= dsz[v];
}
void compress(int u) {
int v = u;
vector<int> vec;
while(true) {
vec.pb(v);
v = edgatv[v].back();
v = find(v);
if(v == u) break;
}
int ant = vec[0];
for(int i = 1; i < vec.size(); i++) {
join(ant,vec[i]);
ant = find(ant);
}
q.push(find(u));
}
int T;
void dfs(int u) {
nx[u] = find(nx[u]);
u = nx[u];
while(edgatv[u].size() && find(edgatv[u].back()) == u) edgatv[u].pop_back();
if(edgatv[u].size() == 0) return;
mark[u] = T;
int v = edgatv[u].back();
v = find(v);
nx[v] = find(nx[v]);
if(mark[nx[v]] == T) {
compress(v);
}
else {
dfs(v);
nx[u] = nx[v];
}
}
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 = 0; i < m; i++) {
int u = U[i];
int v = V[i];
int c = C[i];
edgblk[u][c].pb(v); dsz[u]++;
edgblk[v][c].pb(u); dsz[v]++;
}
for(int i = 0; i < n; i++) {
ds[i] = i; dsz[i]++;
keys[i].insert(r[i]); dsz[i]++;
nx[i] = i;
if(edgblk[i].count(r[i])) {
for(auto x : edgblk[i][r[i]]) {
edgatv[i].pb(x);
}
edgblk[i].erase(r[i]);
}
}
for(int i = 0; i < n; i++) {
q.push(i);
}
while(q.size()) {
int i = q.front(); q.pop();
if(i != find(i)) continue;
T++;
dfs(i);
}
for(int i = 0; i < n; i++) {
if(i != find(i)) continue;
while(edgatv[i].size() && find(edgatv[i].back()) == i) edgatv[i].pop_back();
}
vector<int> ans(n,0);
map<int,int> fq;
for(int i = 0; i < n; i++) {
if(edgatv[find(i)].size() == 0) fq[find(i)]++;
}
int mn = inf;
for(auto x : fq) mn = min(mn,x.sc);
for(int i = 0; i < n; i++) {
if(fq[find(i)] == mn && edgatv[find(i)].size() == 0) ans[i] = 1;
}
return ans;
}
Compilation message
keys.cpp: In function 'void compress(int)':
keys.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i = 1; i < vec.size(); i++) {
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
40148 KB |
Output is correct |
2 |
Correct |
20 ms |
40148 KB |
Output is correct |
3 |
Correct |
21 ms |
40148 KB |
Output is correct |
4 |
Correct |
24 ms |
40252 KB |
Output is correct |
5 |
Correct |
22 ms |
40240 KB |
Output is correct |
6 |
Correct |
25 ms |
40248 KB |
Output is correct |
7 |
Correct |
21 ms |
40316 KB |
Output is correct |
8 |
Correct |
22 ms |
40276 KB |
Output is correct |
9 |
Correct |
21 ms |
40204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
40148 KB |
Output is correct |
2 |
Correct |
20 ms |
40148 KB |
Output is correct |
3 |
Correct |
21 ms |
40148 KB |
Output is correct |
4 |
Correct |
24 ms |
40252 KB |
Output is correct |
5 |
Correct |
22 ms |
40240 KB |
Output is correct |
6 |
Correct |
25 ms |
40248 KB |
Output is correct |
7 |
Correct |
21 ms |
40316 KB |
Output is correct |
8 |
Correct |
22 ms |
40276 KB |
Output is correct |
9 |
Correct |
21 ms |
40204 KB |
Output is correct |
10 |
Correct |
21 ms |
40320 KB |
Output is correct |
11 |
Correct |
21 ms |
40256 KB |
Output is correct |
12 |
Correct |
21 ms |
40336 KB |
Output is correct |
13 |
Correct |
25 ms |
40156 KB |
Output is correct |
14 |
Correct |
20 ms |
40200 KB |
Output is correct |
15 |
Correct |
21 ms |
40276 KB |
Output is correct |
16 |
Correct |
26 ms |
40148 KB |
Output is correct |
17 |
Correct |
21 ms |
40252 KB |
Output is correct |
18 |
Correct |
25 ms |
40276 KB |
Output is correct |
19 |
Correct |
22 ms |
40148 KB |
Output is correct |
20 |
Correct |
21 ms |
40260 KB |
Output is correct |
21 |
Correct |
20 ms |
40228 KB |
Output is correct |
22 |
Correct |
21 ms |
40200 KB |
Output is correct |
23 |
Correct |
21 ms |
40312 KB |
Output is correct |
24 |
Correct |
21 ms |
40340 KB |
Output is correct |
25 |
Correct |
20 ms |
40276 KB |
Output is correct |
26 |
Correct |
21 ms |
40352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
40148 KB |
Output is correct |
2 |
Correct |
20 ms |
40148 KB |
Output is correct |
3 |
Correct |
21 ms |
40148 KB |
Output is correct |
4 |
Correct |
24 ms |
40252 KB |
Output is correct |
5 |
Correct |
22 ms |
40240 KB |
Output is correct |
6 |
Correct |
25 ms |
40248 KB |
Output is correct |
7 |
Correct |
21 ms |
40316 KB |
Output is correct |
8 |
Correct |
22 ms |
40276 KB |
Output is correct |
9 |
Correct |
21 ms |
40204 KB |
Output is correct |
10 |
Correct |
21 ms |
40320 KB |
Output is correct |
11 |
Correct |
21 ms |
40256 KB |
Output is correct |
12 |
Correct |
21 ms |
40336 KB |
Output is correct |
13 |
Correct |
25 ms |
40156 KB |
Output is correct |
14 |
Correct |
20 ms |
40200 KB |
Output is correct |
15 |
Correct |
21 ms |
40276 KB |
Output is correct |
16 |
Correct |
26 ms |
40148 KB |
Output is correct |
17 |
Correct |
21 ms |
40252 KB |
Output is correct |
18 |
Correct |
25 ms |
40276 KB |
Output is correct |
19 |
Correct |
22 ms |
40148 KB |
Output is correct |
20 |
Correct |
21 ms |
40260 KB |
Output is correct |
21 |
Correct |
20 ms |
40228 KB |
Output is correct |
22 |
Correct |
21 ms |
40200 KB |
Output is correct |
23 |
Correct |
21 ms |
40312 KB |
Output is correct |
24 |
Correct |
21 ms |
40340 KB |
Output is correct |
25 |
Correct |
20 ms |
40276 KB |
Output is correct |
26 |
Correct |
21 ms |
40352 KB |
Output is correct |
27 |
Correct |
25 ms |
41208 KB |
Output is correct |
28 |
Correct |
24 ms |
41212 KB |
Output is correct |
29 |
Correct |
22 ms |
41112 KB |
Output is correct |
30 |
Correct |
23 ms |
40660 KB |
Output is correct |
31 |
Correct |
23 ms |
40660 KB |
Output is correct |
32 |
Correct |
22 ms |
40268 KB |
Output is correct |
33 |
Correct |
28 ms |
40648 KB |
Output is correct |
34 |
Correct |
23 ms |
40656 KB |
Output is correct |
35 |
Correct |
24 ms |
40588 KB |
Output is correct |
36 |
Correct |
23 ms |
41172 KB |
Output is correct |
37 |
Correct |
25 ms |
41164 KB |
Output is correct |
38 |
Correct |
23 ms |
41324 KB |
Output is correct |
39 |
Correct |
23 ms |
41300 KB |
Output is correct |
40 |
Correct |
23 ms |
40788 KB |
Output is correct |
41 |
Correct |
24 ms |
40812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
40148 KB |
Output is correct |
2 |
Correct |
20 ms |
40148 KB |
Output is correct |
3 |
Correct |
21 ms |
40148 KB |
Output is correct |
4 |
Correct |
24 ms |
40252 KB |
Output is correct |
5 |
Correct |
22 ms |
40240 KB |
Output is correct |
6 |
Correct |
25 ms |
40248 KB |
Output is correct |
7 |
Correct |
21 ms |
40316 KB |
Output is correct |
8 |
Correct |
22 ms |
40276 KB |
Output is correct |
9 |
Correct |
21 ms |
40204 KB |
Output is correct |
10 |
Correct |
2710 ms |
113172 KB |
Output is correct |
11 |
Correct |
667 ms |
150272 KB |
Output is correct |
12 |
Correct |
160 ms |
64536 KB |
Output is correct |
13 |
Correct |
981 ms |
160700 KB |
Output is correct |
14 |
Correct |
354 ms |
173712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
40148 KB |
Output is correct |
2 |
Correct |
20 ms |
40148 KB |
Output is correct |
3 |
Correct |
21 ms |
40148 KB |
Output is correct |
4 |
Correct |
24 ms |
40252 KB |
Output is correct |
5 |
Correct |
22 ms |
40240 KB |
Output is correct |
6 |
Correct |
25 ms |
40248 KB |
Output is correct |
7 |
Correct |
21 ms |
40316 KB |
Output is correct |
8 |
Correct |
22 ms |
40276 KB |
Output is correct |
9 |
Correct |
21 ms |
40204 KB |
Output is correct |
10 |
Correct |
21 ms |
40320 KB |
Output is correct |
11 |
Correct |
21 ms |
40256 KB |
Output is correct |
12 |
Correct |
21 ms |
40336 KB |
Output is correct |
13 |
Correct |
25 ms |
40156 KB |
Output is correct |
14 |
Correct |
20 ms |
40200 KB |
Output is correct |
15 |
Correct |
21 ms |
40276 KB |
Output is correct |
16 |
Correct |
26 ms |
40148 KB |
Output is correct |
17 |
Correct |
21 ms |
40252 KB |
Output is correct |
18 |
Correct |
25 ms |
40276 KB |
Output is correct |
19 |
Correct |
22 ms |
40148 KB |
Output is correct |
20 |
Correct |
21 ms |
40260 KB |
Output is correct |
21 |
Correct |
20 ms |
40228 KB |
Output is correct |
22 |
Correct |
21 ms |
40200 KB |
Output is correct |
23 |
Correct |
21 ms |
40312 KB |
Output is correct |
24 |
Correct |
21 ms |
40340 KB |
Output is correct |
25 |
Correct |
20 ms |
40276 KB |
Output is correct |
26 |
Correct |
21 ms |
40352 KB |
Output is correct |
27 |
Correct |
25 ms |
41208 KB |
Output is correct |
28 |
Correct |
24 ms |
41212 KB |
Output is correct |
29 |
Correct |
22 ms |
41112 KB |
Output is correct |
30 |
Correct |
23 ms |
40660 KB |
Output is correct |
31 |
Correct |
23 ms |
40660 KB |
Output is correct |
32 |
Correct |
22 ms |
40268 KB |
Output is correct |
33 |
Correct |
28 ms |
40648 KB |
Output is correct |
34 |
Correct |
23 ms |
40656 KB |
Output is correct |
35 |
Correct |
24 ms |
40588 KB |
Output is correct |
36 |
Correct |
23 ms |
41172 KB |
Output is correct |
37 |
Correct |
25 ms |
41164 KB |
Output is correct |
38 |
Correct |
23 ms |
41324 KB |
Output is correct |
39 |
Correct |
23 ms |
41300 KB |
Output is correct |
40 |
Correct |
23 ms |
40788 KB |
Output is correct |
41 |
Correct |
24 ms |
40812 KB |
Output is correct |
42 |
Correct |
2710 ms |
113172 KB |
Output is correct |
43 |
Correct |
667 ms |
150272 KB |
Output is correct |
44 |
Correct |
160 ms |
64536 KB |
Output is correct |
45 |
Correct |
981 ms |
160700 KB |
Output is correct |
46 |
Correct |
354 ms |
173712 KB |
Output is correct |
47 |
Correct |
21 ms |
40148 KB |
Output is correct |
48 |
Correct |
22 ms |
40228 KB |
Output is correct |
49 |
Correct |
21 ms |
40228 KB |
Output is correct |
50 |
Correct |
355 ms |
160172 KB |
Output is correct |
51 |
Correct |
432 ms |
158232 KB |
Output is correct |
52 |
Correct |
458 ms |
138080 KB |
Output is correct |
53 |
Correct |
466 ms |
138088 KB |
Output is correct |
54 |
Correct |
476 ms |
138116 KB |
Output is correct |
55 |
Correct |
639 ms |
126812 KB |
Output is correct |
56 |
Correct |
633 ms |
178124 KB |
Output is correct |
57 |
Correct |
517 ms |
168184 KB |
Output is correct |
58 |
Correct |
678 ms |
185056 KB |
Output is correct |
59 |
Correct |
915 ms |
170168 KB |
Output is correct |
60 |
Correct |
700 ms |
153084 KB |
Output is correct |
61 |
Correct |
923 ms |
165776 KB |
Output is correct |
62 |
Correct |
1236 ms |
170380 KB |
Output is correct |
63 |
Correct |
438 ms |
132836 KB |
Output is correct |
64 |
Correct |
26 ms |
42580 KB |
Output is correct |
65 |
Correct |
26 ms |
42580 KB |
Output is correct |
66 |
Correct |
1264 ms |
170160 KB |
Output is correct |
67 |
Correct |
54 ms |
53588 KB |
Output is correct |
68 |
Correct |
85 ms |
62428 KB |
Output is correct |
69 |
Correct |
941 ms |
170976 KB |
Output is correct |
70 |
Correct |
142 ms |
84556 KB |
Output is correct |
71 |
Correct |
372 ms |
173892 KB |
Output is correct |
72 |
Correct |
983 ms |
170976 KB |
Output is correct |
73 |
Correct |
1248 ms |
170124 KB |
Output is correct |