# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
702099 |
2023-02-22T20:51:10 Z |
Lobo |
Keys (IOI21_keys) |
C++17 |
|
2798 ms |
167920 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];
set<int> keys[maxn];
vector<int> edgatv[maxn];
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 |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35496 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
20 ms |
35540 KB |
Output is correct |
6 |
Correct |
17 ms |
35556 KB |
Output is correct |
7 |
Correct |
17 ms |
35480 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35496 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
20 ms |
35540 KB |
Output is correct |
6 |
Correct |
17 ms |
35556 KB |
Output is correct |
7 |
Correct |
17 ms |
35480 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35468 KB |
Output is correct |
10 |
Correct |
20 ms |
35592 KB |
Output is correct |
11 |
Correct |
17 ms |
35540 KB |
Output is correct |
12 |
Correct |
17 ms |
35540 KB |
Output is correct |
13 |
Correct |
17 ms |
35540 KB |
Output is correct |
14 |
Correct |
17 ms |
35552 KB |
Output is correct |
15 |
Correct |
17 ms |
35540 KB |
Output is correct |
16 |
Correct |
18 ms |
35560 KB |
Output is correct |
17 |
Correct |
17 ms |
35496 KB |
Output is correct |
18 |
Correct |
17 ms |
35580 KB |
Output is correct |
19 |
Correct |
17 ms |
35548 KB |
Output is correct |
20 |
Correct |
17 ms |
35540 KB |
Output is correct |
21 |
Correct |
17 ms |
35528 KB |
Output is correct |
22 |
Correct |
18 ms |
35552 KB |
Output is correct |
23 |
Correct |
17 ms |
35552 KB |
Output is correct |
24 |
Correct |
17 ms |
35616 KB |
Output is correct |
25 |
Correct |
19 ms |
35548 KB |
Output is correct |
26 |
Correct |
20 ms |
35632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35496 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
20 ms |
35540 KB |
Output is correct |
6 |
Correct |
17 ms |
35556 KB |
Output is correct |
7 |
Correct |
17 ms |
35480 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35468 KB |
Output is correct |
10 |
Correct |
20 ms |
35592 KB |
Output is correct |
11 |
Correct |
17 ms |
35540 KB |
Output is correct |
12 |
Correct |
17 ms |
35540 KB |
Output is correct |
13 |
Correct |
17 ms |
35540 KB |
Output is correct |
14 |
Correct |
17 ms |
35552 KB |
Output is correct |
15 |
Correct |
17 ms |
35540 KB |
Output is correct |
16 |
Correct |
18 ms |
35560 KB |
Output is correct |
17 |
Correct |
17 ms |
35496 KB |
Output is correct |
18 |
Correct |
17 ms |
35580 KB |
Output is correct |
19 |
Correct |
17 ms |
35548 KB |
Output is correct |
20 |
Correct |
17 ms |
35540 KB |
Output is correct |
21 |
Correct |
17 ms |
35528 KB |
Output is correct |
22 |
Correct |
18 ms |
35552 KB |
Output is correct |
23 |
Correct |
17 ms |
35552 KB |
Output is correct |
24 |
Correct |
17 ms |
35616 KB |
Output is correct |
25 |
Correct |
19 ms |
35548 KB |
Output is correct |
26 |
Correct |
20 ms |
35632 KB |
Output is correct |
27 |
Correct |
20 ms |
36152 KB |
Output is correct |
28 |
Correct |
21 ms |
36200 KB |
Output is correct |
29 |
Correct |
18 ms |
36192 KB |
Output is correct |
30 |
Correct |
18 ms |
35792 KB |
Output is correct |
31 |
Correct |
18 ms |
35792 KB |
Output is correct |
32 |
Correct |
18 ms |
35672 KB |
Output is correct |
33 |
Correct |
18 ms |
35824 KB |
Output is correct |
34 |
Correct |
18 ms |
35828 KB |
Output is correct |
35 |
Correct |
18 ms |
35844 KB |
Output is correct |
36 |
Correct |
21 ms |
36244 KB |
Output is correct |
37 |
Correct |
19 ms |
36180 KB |
Output is correct |
38 |
Correct |
19 ms |
36368 KB |
Output is correct |
39 |
Correct |
19 ms |
36236 KB |
Output is correct |
40 |
Correct |
18 ms |
35872 KB |
Output is correct |
41 |
Correct |
19 ms |
36088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35496 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
20 ms |
35540 KB |
Output is correct |
6 |
Correct |
17 ms |
35556 KB |
Output is correct |
7 |
Correct |
17 ms |
35480 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35468 KB |
Output is correct |
10 |
Correct |
2798 ms |
101692 KB |
Output is correct |
11 |
Correct |
514 ms |
89348 KB |
Output is correct |
12 |
Correct |
150 ms |
54124 KB |
Output is correct |
13 |
Correct |
739 ms |
119872 KB |
Output is correct |
14 |
Correct |
248 ms |
118160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
19 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35496 KB |
Output is correct |
4 |
Correct |
19 ms |
35540 KB |
Output is correct |
5 |
Correct |
20 ms |
35540 KB |
Output is correct |
6 |
Correct |
17 ms |
35556 KB |
Output is correct |
7 |
Correct |
17 ms |
35480 KB |
Output is correct |
8 |
Correct |
17 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35468 KB |
Output is correct |
10 |
Correct |
20 ms |
35592 KB |
Output is correct |
11 |
Correct |
17 ms |
35540 KB |
Output is correct |
12 |
Correct |
17 ms |
35540 KB |
Output is correct |
13 |
Correct |
17 ms |
35540 KB |
Output is correct |
14 |
Correct |
17 ms |
35552 KB |
Output is correct |
15 |
Correct |
17 ms |
35540 KB |
Output is correct |
16 |
Correct |
18 ms |
35560 KB |
Output is correct |
17 |
Correct |
17 ms |
35496 KB |
Output is correct |
18 |
Correct |
17 ms |
35580 KB |
Output is correct |
19 |
Correct |
17 ms |
35548 KB |
Output is correct |
20 |
Correct |
17 ms |
35540 KB |
Output is correct |
21 |
Correct |
17 ms |
35528 KB |
Output is correct |
22 |
Correct |
18 ms |
35552 KB |
Output is correct |
23 |
Correct |
17 ms |
35552 KB |
Output is correct |
24 |
Correct |
17 ms |
35616 KB |
Output is correct |
25 |
Correct |
19 ms |
35548 KB |
Output is correct |
26 |
Correct |
20 ms |
35632 KB |
Output is correct |
27 |
Correct |
20 ms |
36152 KB |
Output is correct |
28 |
Correct |
21 ms |
36200 KB |
Output is correct |
29 |
Correct |
18 ms |
36192 KB |
Output is correct |
30 |
Correct |
18 ms |
35792 KB |
Output is correct |
31 |
Correct |
18 ms |
35792 KB |
Output is correct |
32 |
Correct |
18 ms |
35672 KB |
Output is correct |
33 |
Correct |
18 ms |
35824 KB |
Output is correct |
34 |
Correct |
18 ms |
35828 KB |
Output is correct |
35 |
Correct |
18 ms |
35844 KB |
Output is correct |
36 |
Correct |
21 ms |
36244 KB |
Output is correct |
37 |
Correct |
19 ms |
36180 KB |
Output is correct |
38 |
Correct |
19 ms |
36368 KB |
Output is correct |
39 |
Correct |
19 ms |
36236 KB |
Output is correct |
40 |
Correct |
18 ms |
35872 KB |
Output is correct |
41 |
Correct |
19 ms |
36088 KB |
Output is correct |
42 |
Correct |
2798 ms |
101692 KB |
Output is correct |
43 |
Correct |
514 ms |
89348 KB |
Output is correct |
44 |
Correct |
150 ms |
54124 KB |
Output is correct |
45 |
Correct |
739 ms |
119872 KB |
Output is correct |
46 |
Correct |
248 ms |
118160 KB |
Output is correct |
47 |
Correct |
17 ms |
35532 KB |
Output is correct |
48 |
Correct |
18 ms |
35560 KB |
Output is correct |
49 |
Correct |
17 ms |
35528 KB |
Output is correct |
50 |
Correct |
259 ms |
103724 KB |
Output is correct |
51 |
Correct |
284 ms |
104936 KB |
Output is correct |
52 |
Correct |
401 ms |
108760 KB |
Output is correct |
53 |
Correct |
405 ms |
108684 KB |
Output is correct |
54 |
Correct |
403 ms |
108688 KB |
Output is correct |
55 |
Correct |
774 ms |
124052 KB |
Output is correct |
56 |
Correct |
536 ms |
131324 KB |
Output is correct |
57 |
Correct |
374 ms |
119784 KB |
Output is correct |
58 |
Correct |
723 ms |
138608 KB |
Output is correct |
59 |
Correct |
1096 ms |
146448 KB |
Output is correct |
60 |
Correct |
569 ms |
127772 KB |
Output is correct |
61 |
Correct |
949 ms |
141108 KB |
Output is correct |
62 |
Correct |
1098 ms |
167916 KB |
Output is correct |
63 |
Correct |
371 ms |
114272 KB |
Output is correct |
64 |
Correct |
22 ms |
37068 KB |
Output is correct |
65 |
Correct |
21 ms |
37084 KB |
Output is correct |
66 |
Correct |
1113 ms |
167888 KB |
Output is correct |
67 |
Correct |
45 ms |
43784 KB |
Output is correct |
68 |
Correct |
55 ms |
49360 KB |
Output is correct |
69 |
Correct |
1111 ms |
147436 KB |
Output is correct |
70 |
Correct |
108 ms |
62840 KB |
Output is correct |
71 |
Correct |
251 ms |
118728 KB |
Output is correct |
72 |
Correct |
1163 ms |
147608 KB |
Output is correct |
73 |
Correct |
1055 ms |
167920 KB |
Output is correct |