# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
459240 |
2021-08-08T10:59:36 Z |
ftkbrian |
Keys (IOI21_keys) |
C++17 |
|
3000 ms |
1700780 KB |
#include "keys.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define f first
#define s second
int par[303030],sz[303030],chk[303030];
vector<int> V[303030],ss[303030];
vector<pii> G[303030];
int Find(int p) {
if(par[p] == p) return p;
return par[p] = Find(par[p]);
}
void add(int t) {
if(chk[t]) return;
chk[t] = 1;
for(auto q : G[t]) {
int a = q.f,b = q.s;
par[a] = Find(a);
par[b] = Find(b);
if(sz[a] > sz[b]) swap(a,b);
if(par[a] == par[b]) continue;
sz[par[b]] += sz[par[a]]; sz[par[a]] = 0;
for(auto t : V[par[a]]) {
V[par[b]].push_back(t);
}
V[par[a]].clear();
par[par[a]] = par[b];
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
vector<int> ans(r.size(), -1);
int n = r.size(),mi = n;
for(int i = 0 ; i < c.size() ; i++) {
if(u[i] > v[i]) swap(u[i],v[i]);
G[c[i]].push_back({u[i],v[i]});
if(r[u[i]] == r[v[i]] && r[u[i]] == c[i]) ss[u[i]].push_back(v[i]);
}
for(int i = 0 ; i < n ; i++) {
sort(G[i].begin(),G[i].end());
G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
}
for(int i = 0 ; i < n ; i++) {
if(ans[i] != -1) continue;
for(int q = 0 ; q < n ; q++) {
par[q] = q,sz[q] = 1;
V[q].clear(); V[q].push_back(r[q]);
chk[q] = 0;
}
while(1) {
int a = Find(i);
if(V[a].empty()) break;
int t = V[a].back(); V[a].pop_back();
add(t);
}
par[i] = Find(i);
ans[i] = sz[par[i]];
for(auto q : ss[i]) ans[q] = ans[i];
}
for(int i = 0 ; i < n ; i++) {
mi = min(mi,ans[i]);
}
for(int i = 0 ; i < n ; i++) {
if(mi == ans[i]) ans[i] = 1;
else ans[i] = 0;
}
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:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0 ; i < c.size() ; i++) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
21580 KB |
Output is correct |
2 |
Correct |
12 ms |
21580 KB |
Output is correct |
3 |
Correct |
12 ms |
21580 KB |
Output is correct |
4 |
Correct |
14 ms |
21708 KB |
Output is correct |
5 |
Correct |
12 ms |
21552 KB |
Output is correct |
6 |
Correct |
12 ms |
21580 KB |
Output is correct |
7 |
Correct |
14 ms |
21560 KB |
Output is correct |
8 |
Correct |
14 ms |
21580 KB |
Output is correct |
9 |
Correct |
15 ms |
21648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
21580 KB |
Output is correct |
2 |
Correct |
12 ms |
21580 KB |
Output is correct |
3 |
Correct |
12 ms |
21580 KB |
Output is correct |
4 |
Correct |
14 ms |
21708 KB |
Output is correct |
5 |
Correct |
12 ms |
21552 KB |
Output is correct |
6 |
Correct |
12 ms |
21580 KB |
Output is correct |
7 |
Correct |
14 ms |
21560 KB |
Output is correct |
8 |
Correct |
14 ms |
21580 KB |
Output is correct |
9 |
Correct |
15 ms |
21648 KB |
Output is correct |
10 |
Correct |
13 ms |
21592 KB |
Output is correct |
11 |
Correct |
13 ms |
21648 KB |
Output is correct |
12 |
Correct |
13 ms |
21628 KB |
Output is correct |
13 |
Correct |
14 ms |
21620 KB |
Output is correct |
14 |
Correct |
13 ms |
21604 KB |
Output is correct |
15 |
Correct |
14 ms |
21580 KB |
Output is correct |
16 |
Correct |
13 ms |
21580 KB |
Output is correct |
17 |
Correct |
14 ms |
21580 KB |
Output is correct |
18 |
Correct |
13 ms |
21652 KB |
Output is correct |
19 |
Correct |
12 ms |
21580 KB |
Output is correct |
20 |
Correct |
13 ms |
21652 KB |
Output is correct |
21 |
Correct |
17 ms |
21632 KB |
Output is correct |
22 |
Correct |
15 ms |
21676 KB |
Output is correct |
23 |
Correct |
15 ms |
21780 KB |
Output is correct |
24 |
Correct |
14 ms |
21580 KB |
Output is correct |
25 |
Correct |
14 ms |
21580 KB |
Output is correct |
26 |
Correct |
16 ms |
21620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
21580 KB |
Output is correct |
2 |
Correct |
12 ms |
21580 KB |
Output is correct |
3 |
Correct |
12 ms |
21580 KB |
Output is correct |
4 |
Correct |
14 ms |
21708 KB |
Output is correct |
5 |
Correct |
12 ms |
21552 KB |
Output is correct |
6 |
Correct |
12 ms |
21580 KB |
Output is correct |
7 |
Correct |
14 ms |
21560 KB |
Output is correct |
8 |
Correct |
14 ms |
21580 KB |
Output is correct |
9 |
Correct |
15 ms |
21648 KB |
Output is correct |
10 |
Correct |
13 ms |
21592 KB |
Output is correct |
11 |
Correct |
13 ms |
21648 KB |
Output is correct |
12 |
Correct |
13 ms |
21628 KB |
Output is correct |
13 |
Correct |
14 ms |
21620 KB |
Output is correct |
14 |
Correct |
13 ms |
21604 KB |
Output is correct |
15 |
Correct |
14 ms |
21580 KB |
Output is correct |
16 |
Correct |
13 ms |
21580 KB |
Output is correct |
17 |
Correct |
14 ms |
21580 KB |
Output is correct |
18 |
Correct |
13 ms |
21652 KB |
Output is correct |
19 |
Correct |
12 ms |
21580 KB |
Output is correct |
20 |
Correct |
13 ms |
21652 KB |
Output is correct |
21 |
Correct |
17 ms |
21632 KB |
Output is correct |
22 |
Correct |
15 ms |
21676 KB |
Output is correct |
23 |
Correct |
15 ms |
21780 KB |
Output is correct |
24 |
Correct |
14 ms |
21580 KB |
Output is correct |
25 |
Correct |
14 ms |
21580 KB |
Output is correct |
26 |
Correct |
16 ms |
21620 KB |
Output is correct |
27 |
Correct |
80 ms |
21896 KB |
Output is correct |
28 |
Correct |
82 ms |
21888 KB |
Output is correct |
29 |
Correct |
94 ms |
21836 KB |
Output is correct |
30 |
Correct |
63 ms |
21780 KB |
Output is correct |
31 |
Correct |
17 ms |
21708 KB |
Output is correct |
32 |
Correct |
14 ms |
21792 KB |
Output is correct |
33 |
Correct |
17 ms |
21708 KB |
Output is correct |
34 |
Correct |
262 ms |
22436 KB |
Output is correct |
35 |
Correct |
142 ms |
22084 KB |
Output is correct |
36 |
Correct |
903 ms |
23748 KB |
Output is correct |
37 |
Correct |
123 ms |
21836 KB |
Output is correct |
38 |
Correct |
580 ms |
22336 KB |
Output is correct |
39 |
Correct |
203 ms |
21888 KB |
Output is correct |
40 |
Correct |
62 ms |
24028 KB |
Output is correct |
41 |
Correct |
835 ms |
25908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
21580 KB |
Output is correct |
2 |
Correct |
12 ms |
21580 KB |
Output is correct |
3 |
Correct |
12 ms |
21580 KB |
Output is correct |
4 |
Correct |
14 ms |
21708 KB |
Output is correct |
5 |
Correct |
12 ms |
21552 KB |
Output is correct |
6 |
Correct |
12 ms |
21580 KB |
Output is correct |
7 |
Correct |
14 ms |
21560 KB |
Output is correct |
8 |
Correct |
14 ms |
21580 KB |
Output is correct |
9 |
Correct |
15 ms |
21648 KB |
Output is correct |
10 |
Execution timed out |
3191 ms |
1700780 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
21580 KB |
Output is correct |
2 |
Correct |
12 ms |
21580 KB |
Output is correct |
3 |
Correct |
12 ms |
21580 KB |
Output is correct |
4 |
Correct |
14 ms |
21708 KB |
Output is correct |
5 |
Correct |
12 ms |
21552 KB |
Output is correct |
6 |
Correct |
12 ms |
21580 KB |
Output is correct |
7 |
Correct |
14 ms |
21560 KB |
Output is correct |
8 |
Correct |
14 ms |
21580 KB |
Output is correct |
9 |
Correct |
15 ms |
21648 KB |
Output is correct |
10 |
Correct |
13 ms |
21592 KB |
Output is correct |
11 |
Correct |
13 ms |
21648 KB |
Output is correct |
12 |
Correct |
13 ms |
21628 KB |
Output is correct |
13 |
Correct |
14 ms |
21620 KB |
Output is correct |
14 |
Correct |
13 ms |
21604 KB |
Output is correct |
15 |
Correct |
14 ms |
21580 KB |
Output is correct |
16 |
Correct |
13 ms |
21580 KB |
Output is correct |
17 |
Correct |
14 ms |
21580 KB |
Output is correct |
18 |
Correct |
13 ms |
21652 KB |
Output is correct |
19 |
Correct |
12 ms |
21580 KB |
Output is correct |
20 |
Correct |
13 ms |
21652 KB |
Output is correct |
21 |
Correct |
17 ms |
21632 KB |
Output is correct |
22 |
Correct |
15 ms |
21676 KB |
Output is correct |
23 |
Correct |
15 ms |
21780 KB |
Output is correct |
24 |
Correct |
14 ms |
21580 KB |
Output is correct |
25 |
Correct |
14 ms |
21580 KB |
Output is correct |
26 |
Correct |
16 ms |
21620 KB |
Output is correct |
27 |
Correct |
80 ms |
21896 KB |
Output is correct |
28 |
Correct |
82 ms |
21888 KB |
Output is correct |
29 |
Correct |
94 ms |
21836 KB |
Output is correct |
30 |
Correct |
63 ms |
21780 KB |
Output is correct |
31 |
Correct |
17 ms |
21708 KB |
Output is correct |
32 |
Correct |
14 ms |
21792 KB |
Output is correct |
33 |
Correct |
17 ms |
21708 KB |
Output is correct |
34 |
Correct |
262 ms |
22436 KB |
Output is correct |
35 |
Correct |
142 ms |
22084 KB |
Output is correct |
36 |
Correct |
903 ms |
23748 KB |
Output is correct |
37 |
Correct |
123 ms |
21836 KB |
Output is correct |
38 |
Correct |
580 ms |
22336 KB |
Output is correct |
39 |
Correct |
203 ms |
21888 KB |
Output is correct |
40 |
Correct |
62 ms |
24028 KB |
Output is correct |
41 |
Correct |
835 ms |
25908 KB |
Output is correct |
42 |
Execution timed out |
3191 ms |
1700780 KB |
Time limit exceeded |
43 |
Halted |
0 ms |
0 KB |
- |