QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115559#4926. Where Is the Root?jamielim0 5ms3708kbC++142.3kb2023-06-26 11:45:282023-06-26 11:45:58

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-26 11:45:58]
  • 评测
  • 测评结果:0
  • 用时:5ms
  • 内存:3708kb
  • [2023-06-26 11:45:28]
  • 提交

answer

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

#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const ll MOD=1000000007;

int n;
vector<int> adj[505];
int dist[2][505];
int fr;
int dep[505];
int maxdep;
vector<int> leaf;
bool lf[505];

void findFakeRoot(){
	for(int i=1;i<=n;i++)dist[0][i]=dist[1][i]=INF;
	dist[0][1]=0;
	queue<int> q;
	q.push(1);
	int maxi=1;
	while(!q.empty()){
		int cur=q.front();q.pop();
		for(int i:adj[cur]){
			if(dist[0][i]>dist[0][cur]+1){
				dist[0][i]=dist[0][cur]+1;
				q.push(i);
				if(dist[0][i]>dist[0][maxi])maxi=i;
			}
		}
	}
	dist[1][maxi]=0;
	q.push(maxi);
	while(!q.empty()){
		int cur=q.front();q.pop();
		for(int i:adj[cur]){
			if(dist[1][i]>dist[1][cur]+1){
				dist[1][i]=dist[1][cur]+1;
				q.push(i);
				if(dist[1][i]>dist[1][maxi])maxi=i;
			}
		}
	}
	fr=maxi;
	while(dist[1][fr]>dist[1][maxi]/2){
		for(int i:adj[fr]){
			if(dist[1][i]==dist[1][fr]-1){
				fr=i;break;
			}
		}
	}
}

void dfs(int x,int p){
	maxdep=max(maxdep,dep[x]);
	int c=0;
	for(int i:adj[x]){
		if(i==p)continue;
		dep[i]=dep[x]+1;
		dfs(i,x);
		c++;
	}
	if(c==0){
		leaf.pb(x);
		lf[x]=1;
	}
}

vector<int> t;
void dfs2(int x,int p,int avoid){
	int c=0;
	for(int i:adj[x]){
		if(i==p)continue;
		if(i==avoid)continue;
		dfs2(i,x,avoid);
		c++;
	}
	if(c==0)t.pb(x);
}
vector<int> getOtherLeaves(int x){
	t.clear();
	dfs2(fr,0,x);
	return t;
}

bool query(vector<int> v){
	sort(ALL(v));
	v.resize(unique(ALL(v))-v.begin());
	printf("? %d",SZ(v));
	for(int i:v)printf(" %d",i);
	printf("\n");
	fflush(stdout);
	char str[5];
	scanf("%s",str);
	if(str[0]=='Y')return 1;
	return 0;
}

int main(){
	scanf("%d",&n);
	int a,b;
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		adj[a].pb(b);adj[b].pb(a);
	}
	for(int i=1;i<=n;i++){
		if(SZ(adj[i])>=3){
			dfs(fr,0);
			break;
		}
	}
	for(int i=1;i<=n;i++){
		if(!lf[i]){
			leaf.pb(i);
			if(query(leaf)){
				printf("! %d\n",i);
				fflush(stdout);
				return 0;
			}else leaf.pop_back();
		}
	}
	
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3672kb

input:

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

output:

? 2 0 1

result:

wrong output format Unexpected end of file - int32 expected

Subtask #2:

score: 0
Wrong Answer

Test #24:

score: 0
Wrong Answer
time: 2ms
memory: 3708kb

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

output:

? 2 0 1

result:

wrong output format Unexpected end of file - int32 expected

Subtask #3:

score: 0
Wrong Answer

Test #54:

score: 0
Wrong Answer
time: 5ms
memory: 3696kb

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:

? 2 0 1

result:

wrong output format Unexpected end of file - int32 expected