#include <bits/stdc++.h>
#include "island.h"
using namespace std;
int N;
vector<int> g[305];
int d[305][305];
int ua[305];
vector<int> ug[305];
void dfs(int x, int par, int root, int depth){
d[root][x] = depth;
d[x][root] = depth;
for (int tgt : g[x]){
if (tgt == par) continue;
dfs(tgt,x,root,depth+1);
}
}
int f(int x){
if (ua[x] == x) return x;
return ua[x] = f(ua[x]);
}
// "All neighbours known"
bool ann[305];
int gi[305];
void merge(int x, int y){
int fx = f(x);
int fy = f(y);
if (f(x) == f(y)){
return;
}
if (ug[fx].size() > ug[fy].size()){
swap(fx,fy);
swap(x,y);
}
g[x].push_back(y);
g[y].push_back(x);
answer(x,y);
if (g[x].size() == N-1){
ann[x] = true;
}
if (g[y].size() == N-1){
ann[y] = true;
}
for (int tgt : ug[fx]){
ug[fy].push_back(tgt);
dfs(tgt,-1,tgt,0);
}
ua[fx] = fy;
ug[fx].clear();
}
void solve(int n, int L) {
N = n;
for (int i = 1; i <= N; i++){
ug[i].push_back(i);
ua[i] = i;
gi[i] = 1;
}
for (int i = N; i > 1; i--){
int ret = query(i,1);
merge(i,ret);
}
ann[1] = true;
for (int cur_ann = 1; cur_ann < N; cur_ann++){
for (int i = 1; i <= cur_ann; i++){
for (int j: g[i]){
if (ann[j]) continue;
bool can_expand = true;
for (int tgt: g[j]){
if (!ann[tgt]) {
can_expand = false;
break;
}
}
if (can_expand){
int ret = query(j,++gi[j]);
if (d[ret][j] == 2){
ann[j] = true;
}
else{
merge(ret,j);
}
}
}
}
ann[cur_ann+1] = true;
}
// int variable_example = query(1, 1);
// for (int i = 2; i <= N; i++) {
// answer(1, i);
// }
}
Compilation message
island.cpp: In function 'void merge(int, int)':
island.cpp:50:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | if (g[x].size() == N-1){
| ~~~~~~~~~~~~^~~~~~
island.cpp:53:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | if (g[y].size() == N-1){
| ~~~~~~~~~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
7 ms |
1288 KB |
Output is correct |
6 |
Correct |
5 ms |
856 KB |
Output is correct |
7 |
Correct |
5 ms |
1112 KB |
Output is correct |
8 |
Correct |
7 ms |
1184 KB |
Output is correct |
9 |
Correct |
6 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1112 KB |
Output is correct |
2 |
Correct |
5 ms |
1232 KB |
Output is correct |
3 |
Correct |
5 ms |
1368 KB |
Output is correct |
4 |
Correct |
4 ms |
856 KB |
Output is correct |
5 |
Correct |
4 ms |
856 KB |
Output is correct |
6 |
Correct |
4 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
1112 KB |
Output is correct |
3 |
Correct |
5 ms |
1456 KB |
Output is correct |
4 |
Correct |
5 ms |
760 KB |
Output is correct |
5 |
Correct |
5 ms |
1112 KB |
Output is correct |
6 |
Correct |
5 ms |
1368 KB |
Output is correct |
7 |
Correct |
6 ms |
1124 KB |
Output is correct |
8 |
Correct |
8 ms |
1368 KB |
Output is correct |
9 |
Correct |
5 ms |
1368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1112 KB |
Output is correct |
2 |
Correct |
5 ms |
1104 KB |
Output is correct |
3 |
Correct |
6 ms |
1420 KB |
Output is correct |
4 |
Correct |
7 ms |
1364 KB |
Output is correct |
5 |
Correct |
5 ms |
1372 KB |
Output is correct |
6 |
Correct |
6 ms |
1368 KB |
Output is correct |
7 |
Correct |
5 ms |
856 KB |
Output is correct |
8 |
Correct |
4 ms |
872 KB |
Output is correct |
9 |
Correct |
4 ms |
1384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
7 ms |
1288 KB |
Output is correct |
6 |
Correct |
5 ms |
856 KB |
Output is correct |
7 |
Correct |
5 ms |
1112 KB |
Output is correct |
8 |
Correct |
7 ms |
1184 KB |
Output is correct |
9 |
Correct |
6 ms |
1108 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
5 ms |
1112 KB |
Output is correct |
12 |
Correct |
5 ms |
1456 KB |
Output is correct |
13 |
Correct |
5 ms |
760 KB |
Output is correct |
14 |
Correct |
5 ms |
1112 KB |
Output is correct |
15 |
Correct |
5 ms |
1368 KB |
Output is correct |
16 |
Correct |
6 ms |
1124 KB |
Output is correct |
17 |
Correct |
8 ms |
1368 KB |
Output is correct |
18 |
Correct |
5 ms |
1368 KB |
Output is correct |
19 |
Incorrect |
4 ms |
856 KB |
Wrong Answer [7] |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
6 ms |
1112 KB |
Output is correct |
5 |
Correct |
5 ms |
1104 KB |
Output is correct |
6 |
Correct |
6 ms |
1420 KB |
Output is correct |
7 |
Correct |
7 ms |
1364 KB |
Output is correct |
8 |
Correct |
5 ms |
1372 KB |
Output is correct |
9 |
Correct |
6 ms |
1368 KB |
Output is correct |
10 |
Correct |
5 ms |
856 KB |
Output is correct |
11 |
Correct |
4 ms |
872 KB |
Output is correct |
12 |
Correct |
4 ms |
1384 KB |
Output is correct |
13 |
Incorrect |
4 ms |
1112 KB |
Wrong Answer [5] |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1112 KB |
Output is correct |
2 |
Correct |
5 ms |
1232 KB |
Output is correct |
3 |
Correct |
5 ms |
1368 KB |
Output is correct |
4 |
Correct |
4 ms |
856 KB |
Output is correct |
5 |
Correct |
4 ms |
856 KB |
Output is correct |
6 |
Correct |
4 ms |
856 KB |
Output is correct |
7 |
Incorrect |
3 ms |
856 KB |
Wrong Answer [5] |
8 |
Halted |
0 ms |
0 KB |
- |