#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;
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 = last - 1; i >= 0; --i){
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
*/
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:81:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:85:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:95:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:99:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int e = 0; e < c[j].size(); ++e){
~~^~~~~~~~~~~~~
icc.cpp:115:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < c[numa].size(); ++i){
~~^~~~~~~~~~~~~~~~
icc.cpp:118:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < c[numb].size(); ++i){
~~^~~~~~~~~~~~~~~~
icc.cpp:53:31: warning: unused variable 'lll' [-Wunused-variable]
int xx = 0, last = 0, lll = 0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
504 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
560 KB |
Ok! 1489 queries used. |
| 2 |
Correct |
192 ms |
692 KB |
Ok! 1494 queries used. |
| 3 |
Correct |
145 ms |
760 KB |
Ok! 1466 queries used. |
| 4 |
Correct |
148 ms |
504 KB |
Ok! 1525 queries used. |
| 5 |
Incorrect |
3 ms |
504 KB |
Wrong road! |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
608 KB |
Ok! 1525 queries used. |
| 2 |
Correct |
137 ms |
612 KB |
Ok! 1329 queries used. |
