| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 599819 |
2022-07-20T01:25:49 Z |
tpiang |
Keys (IOI21_keys) |
C++17 |
|
136 ms |
20860 KB |
#include <bits/stdc++.h>
#define vi vector<int>
using namespace std;
vector<vi> graph;
vi root;
vi sz;
int ro;
void dfs(int u){
root[u] = ro;
for(int v : graph[u]){
if(root[v] == -1){
dfs(v);
sz[u] += sz[v];
}
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = (int) r.size();
int m = (int) c.size();
vector<int> ans(n, 0);
root.assign(n,-1);
graph.assign(n,vi());
sz.assign(n,1);
for(int i = 0; i < n; i++){
if(r[i] != 0){
ans[i] = 1;
}
}
for(int i = 0; i < m; i++){
graph[u[i]].push_back(v[i]);
graph[v[i]].push_back(u[i]);
}
for(int i = 0; i < n; i++){
if(ans[i] == 1) root[i] = i;
if(root[i] == -1 && ans[i] == 0){
ro = i;
dfs(i);
}
}
int mini = 1000;
for(int i = 0; i < n; i++){
mini = min(mini, sz[root[i]]);
}
for(int i = 0; i < n; i++){
if(sz[root[i]] == mini){
ans[i] = 1;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
304 KB |
Output is correct |
| 8 |
Correct |
1 ms |
296 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
304 KB |
Output is correct |
| 8 |
Correct |
1 ms |
296 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
304 KB |
Output is correct |
| 8 |
Correct |
1 ms |
296 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
304 KB |
Output is correct |
| 8 |
Correct |
1 ms |
296 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| 10 |
Incorrect |
136 ms |
20860 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
304 KB |
Output is correct |
| 8 |
Correct |
1 ms |
296 KB |
Output is correct |
| 9 |
Correct |
1 ms |
296 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
304 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
