#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef __WIN32
int ansa, ansb, g[105][105], M;
pair < int, int > p[105];
void setRoad(int a, int b){
cout <<a<<" "<<b<<endl;
int x = p[M].first, y = p[M].second;
M++;
g[x][y] = g[y][x] = 1;
}
int query(int size_a, int size_b, int a[], int b[]){
for (int i = 0; i < size_a; ++i){
for (int j = 0; j < size_b; ++j){
if (g[a[i]][b[j]])return 1;
}
}
return 0;
}
#endif // __WIN32
int n, nm;
bool us[105];
vector < int > c[105], r[105];
void dfs(int x){
us[x] = 1;
c[nm].push_back(x);
for (int i = 0; i < r[x].size(); ++i){
if (!us[r[x][i]])dfs(r[x][i]);
}
}
void run(int N){
n = N;
int a[105], b[105], sza, szb;
for (int it = 1; it < n; ++it){
for (int i = 0; i <= n; ++i)c[i].clear();
nm = 0;
memset(us, 0, sizeof(us));
for (int i = 1; i <= n; ++i){
if (!us[i]){
dfs(i);
nm++;
}
}
int xx = 0, last = 0, lll = 0;
for (int i = 0; ; ++i){
sza = 0, szb = 0;
for (int j = 0; j < nm; ++j){
if (j & (1 << i)){
for (int e = 0; e < c[j].size(); ++e){
a[sza++] = c[j][e];
}
}else {
for (int e = 0; e < c[j].size(); ++e){
b[szb++] = c[j][e];
}
}
}
if (sza == 0 || szb == 0)break;
lll = i;
if (query(sza, szb, a, b)){
xx += (1 << i);
last = i;
}
}
//cout <<xx<<endl;
int numa = 0, numb = (1 << last);
//cout <<numa<<" "<<numb<<endl;
for (int i = lll; i >= 0; --i){
if (i == last)continue;
if (xx & (1 << i)){
sza = szb = 0;
for (int j = 0; j < nm; ++j){
if ((j & (1 << i)) && (j & (1 << last))){
for (int e = 0; e < c[j].size(); ++e){
a[sza++] = c[j][e];
}
}else if (!(j & (1 << i)) && !(j & (1 << last))){
for (int e = 0; e < c[j].size(); ++e){
b[szb++] = c[j][e];
}
}
}
if (sza == 0 || szb == 0 || !query(sza, szb, a, b))numa += (1 << i);else numb += (1 << i);
}else {
sza = szb = 0;
for (int j = 0; j < nm; ++j){
if (!(j & (1 << i)) && (j & (1 << last))){
for (int e = 0; e < c[j].size(); ++e){
a[sza++] = c[j][e];
}
}else if (!(j & (1 << i)) && !(j & (1 << last))){
for (int e = 0; e < c[j].size(); ++e){
b[szb++] = c[j][e];
}
}
}
//cout <<sza<<" "<<szb<<endl;
//for (int i = 0; i < sza; ++i)cout <<a[i]<<" ";cout <<endl;
//for (int i = 0; i < szb; ++i)cout <<b[i]<<" ";cout <<endl;
if (sza == 0 || szb == 0 || !query(sza, szb, a, b)){
numa += (1 << i);
numb += (1 << i);
}
}
}
//cout <<numa<<" "<<numb<<endl;
sza = 0, szb = 0;
for (int i = 0; i < c[numa].size(); ++i){
a[sza++] = c[numa][i];
}
for (int i = 0; i < c[numb].size(); ++i){
b[szb++] = c[numb][i];
}
int l = 0, r = sza - 1;
while (l < r){
int mid = (l + r) / 2;
if (query(mid + 1, szb, a, b))r = mid;else l = mid + 1;
}
int ll = l;
int aa = a[ll];
l = 0, r = szb - 1;
while (l < r){
int mid = (l + r) / 2;
if (query(ll + 1, mid + 1, a, b))r = mid;else l = mid + 1;
}
int rr = l;
int bb = b[rr];
setRoad(aa, bb);
::r[aa].push_back(bb);
::r[bb].push_back(aa);
}
}
#ifdef __WIN32
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin >>n;
for (int i = 1; i < n; ++i)cin >>p[i].first>>p[i].second;
M = 2;
int x = p[1].first, y = p[1].second;
g[x][y] = g[y][x] = 1;
run(n);
}
#endif // __WIN32
/*
4
2 4
1 3
4 1
11
11 10
10 3
3 4
2 3
1 2
2 6
6 8
3 5
5 9
6 7
*/
Compilation message
icc.cpp: In function 'void dfs(int)':
icc.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < r[x].size(); ++i){
~~^~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:58:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:62:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:83:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:87:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:97:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:101:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:117:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < c[numa].size(); ++i){
~~^~~~~~~~~~~~~~~~
icc.cpp:120:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < c[numb].size(); ++i){
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
504 KB |
Ok! 116 queries used. |
| 2 |
Correct |
10 ms |
504 KB |
Ok! 116 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
504 KB |
Ok! 645 queries used. |
| 2 |
Correct |
42 ms |
504 KB |
Ok! 531 queries used. |
| 3 |
Correct |
45 ms |
528 KB |
Ok! 583 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
576 KB |
Ok! 1599 queries used. |
| 2 |
Correct |
136 ms |
504 KB |
Ok! 1287 queries used. |
| 3 |
Correct |
158 ms |
504 KB |
Ok! 1609 queries used. |
| 4 |
Correct |
159 ms |
632 KB |
Ok! 1583 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
600 KB |
Ok! 1566 queries used. |
| 2 |
Correct |
154 ms |
620 KB |
Ok! 1574 queries used. |
| 3 |
Correct |
151 ms |
636 KB |
Ok! 1587 queries used. |
| 4 |
Correct |
159 ms |
636 KB |
Ok! 1593 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
504 KB |
Ok! 1548 queries used. |
| 2 |
Correct |
151 ms |
576 KB |
Ok! 1556 queries used. |
| 3 |
Correct |
147 ms |
504 KB |
Ok! 1520 queries used. |
| 4 |
Correct |
152 ms |
604 KB |
Ok! 1587 queries used. |
| 5 |
Correct |
158 ms |
504 KB |
Ok! 1601 queries used. |
| 6 |
Correct |
156 ms |
504 KB |
Ok! 1602 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
504 KB |
Ok! 1587 queries used. |
| 2 |
Correct |
142 ms |
632 KB |
Ok! 1363 queries used. |
