QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#875037#4926. Where Is the Root?Xiaoyang0 1ms3584kbC++141.6kb2025-01-29 00:53:412025-01-29 00:53:48

Judging History

This is the latest submission verdict.

  • [2025-01-29 00:53:48]
  • Judged
  • Verdict: 0
  • Time: 1ms
  • Memory: 3584kb
  • [2025-01-29 00:53:41]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 1e18;
#define rep(i,a,b) for (ll i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
#define endl "\n"
void inc(ll &a,ll b) {a=(a+b)%mod;}
void dec(ll &a,ll b) {a=(a-b+mod)%mod;}
int lowbit(ll x) {return x&(-x);}


const ll maxn = 555;
vector<ll>alist[maxn];
vector<ll>v;
ll deg[maxn];

bool cmp(ll a,ll b){
	return deg[a]<deg[b];
}

void query(vector<ll>v){
	cout<<"?"<<" ";
	for(auto x:v)cout<<x<<" ";
	cout<<endl;
}

bool check(ll mid){
	vector<ll>tmp;
	rep(i,0,mid+1)tmp.pb(v[i]);
	query(tmp);
	string in;cin>>in;
	if(in=="YES")return 1;
	else return 0;
}
int main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//comment out for interactives 
	ll n;cin>>n;
	rep(i,0,n-1){
		ll a,b;cin>>a>>b;
		alist[a].pb(b);
		alist[b].pb(a);
		deg[a]++;
		deg[b]++;
	}
	rep(i,1,n+1)v.pb(i);
	sort(ALL(v),cmp);
	//at least 3 leaves
	ll lo=0,hi=n-1;
	while(lo<hi-1){
		ll mid=(lo+hi+1)/2;
		if(check(mid)){//lca is in the current prefix
			hi=mid;
		}else{//lca is not in current prefix
			lo=mid;
		}
	}
	
	if(lo==0 and hi==1){
		vector<ll>tmp;
		tmp.pb(v[0]);tmp.pb(v[2]);
		query(tmp);
		string in;cin>>in;
		if(in=="YES")cout<<'!'<<" "<<v[0]<<endl;
		else cout<<'!'<<" "<<v[1]<<endl;
	}else{
		cout<<"!"<<" "<<v[hi]<<endl;
	}
	return 0;
}







详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3584kb

input:

7
4 1
1 2
4 3
3 5
3 6
4 7
NO

output:

? 2 5 6 7 
? 2 5 6 7 1 3 

result:

wrong output format Unexpected end of file - int32 expected

Subtask #2:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 0ms
memory: 3584kb

input:

30
1 15
29 30
1 4
7 28
29 17
1 26
26 7
12 5
27 13
3 7
27 1
21 15
9 22
22 5
24 27
19 1
25 30
22 27
6 15
16 13
18 2
27 10
27 30
20 26
8 15
18 8
14 1
27 23
11 3
NO

output:

? 2 28 25 24 23 21 20 19 17 16 14 12 11 10 9 4 
? 2 28 25 24 23 21 20 19 17 16 14 12 11 10 9 4 6 13 29 3 5 8 18 

result:

wrong output format Unexpected end of file - int32 expected

Subtask #3:

score: 0
Time Limit Exceeded

Test #54:

score: 0
Time Limit Exceeded

input:

500
419 133
44 225
391 269
419 461
293 347
108 31
110 363
423 257
321 155
498 87
180 492
251 5
357 30
341 172
275 109
372 446
286 336
208 339
162 320
138 103
129 219
62 141
359 286
130 238
470 460
418 48
210 358
429 13
323 143
382 415
406 394
309 175
325 170
128 108
6 113
363 17
470 457
7 224
288 48...

output:

? 283 299 298 296 294 292 290 289 287 285 284 300 282 281 280 279 277 276 273 270 268 318 332 331 330 328 327 326 324 323 322 320 264 317 316 313 312 310 307 305 304 303 192 210 209 208 205 204 201 199 198 197 196 211 191 189 181 177 174 173 171 169 168 235 260 257 256 254 252 250 246 245 242 334 23...

result: