#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
#define maxn 105
int a[maxn],b[maxn],par[maxn],in[maxn];
int fp(int i){return par[i]==i?i:par[i]=fp(par[i]);}
void join(int x,int y){par[x]=y;}
vector<int> fill(vector<int> &x){
for(int i:x)in[i]=1;
vector<int> res;
for(int i=1;par[i]!=0;++i){
if(in[fp(i)])res.pb(i);
}
for(int i:x)in[i]=0;
return res;
}
int ask(vector<int> x,vector<int> y){
for(int i=0;i<sz(x);++i)a[i]=x[i];
for(int i=0;i<sz(y);++i)b[i]=y[i];
return query(sz(x),sz(y),a,b);
}
int dnc(vector<int> &x,vector<int> &y){
if(x.size()==1)return x[0];
vector<int> l,r;
for(int i=0;i<sz(x);++i){
if(i<sz(x)/2)l.pb(x[i]);
else r.pb(x[i]);
}
if(ask(l,y))return dnc(l,y);
else return dnc(r,y);
}
void run(int N){
for(int i=1;i<=N;++i)par[i]=i;
for(int _=0;_<N-1;++_){
int curx=0,cury=0;
vector<int> v;
for(int i=1;i<=N;++i){
if(fp(i)==i)v.pb(i);
}
//pf("v: ");for(int x:v)pf("%d ",x);pf("\n");
vector<int> same;
for(int i=1;i<sz(v);i<<=1){
vector<int> l,r;
//pf("%d: %d %d\n",i,curx,cury);
for(int x=0;x<sz(v);++x){
if(x&i)r.pb(v[x]);
else l.pb(v[x]);
}
int res=ask(fill(l),fill(r));
if(res==0){//they are from the same set
//pf("same\n");
same.pb(i);
}
else{//they are from different sets
//pf("diff\n");
vector<int> l,r;
for(int x=0;x<sz(v);++x){
if((curx&x)==curx&&(x&i))l.pb(v[x]);
else if((cury&x)==cury&&!(x&i))r.pb(v[x]);
}
//pf("l: ");for(int x:l)pf("%d ",x);pf("\n");
//pf("r: ");for(int x:r)pf("%d ",x);pf("\n");
if(ask(l,r))curx^=i;
else cury^=i;
}
}
for(int i:same){
//pf("same %d: ",i);
vector<int> l,r;
for(int x=0;x<sz(v);++x){
if((curx&x)==curx&&(x&i))l.pb(v[x]);
else if((cury&x)==cury&&(x&i))r.pb(v[x]);
}
//for(int x:l)pf("%d ",x);pf("\n");
//for(int x:r)pf("%d ",x);pf("\n");
if(ask(fill(l),fill(r)))curx^=i,cury^=i;
}
//pf("%d %d\n",curx,cury);
vector<int> l,r;
for(int i=1;i<=N;++i){
if(fp(i)==v[curx])l.pb(i);
else if(fp(i)==v[cury])r.pb(i);
}
int x=dnc(l,r),y=dnc(r,l);
setRoad(x,y);
join(x,y);
}
}
#ifdef DEBUG
int num_qry;
vector<ii> EL,tmp;
int query(int size_a,int size_b,int a[],int b[]){
++num_qry;
for(int i=0;i<size_a;++i){
for(int j=0;j<size_b;++j){
int x=a[i],y=b[j];
for(auto[a,b]:EL){
if((a==x&&b==y)||(b==x&&a==y))return 1;
}
}
}
return 0;
}
void setRoad(int a,int b){
pf("answer: %d %d\n",a,b);
auto[c,d]=EL.back();
assert((a==c&&b==d)||(a==d&&b==c));
if(!tmp.empty()){
EL.pb(tmp.back());
pf("curedge: %d %d\n",EL.back().fi,EL.back().se);
tmp.pop_back();
}
}
int main(){
int n;sf("%d",&n);
for(int i=0;i<n-1;++i){
int a,b;sf("%d%d",&a,&b);
tmp.pb({a,b});
}
reverse(all(tmp));
EL.pb(tmp.back());
pf("curedge: %d %d\n",EL.back().fi,EL.back().se);
tmp.pop_back();
run(n);
assert(tmp.empty());
pf("AC: %d\n",num_qry);
}
#endif
/*
4
2 4
1 3
1 4
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
468 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
500 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
504 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
468 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
428 KB |
Wrong road! |
| 2 |
Halted |
0 ms |
0 KB |
- |
