QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115557#4926. Where Is the Root?jamielimCompile Error//C++143.6kb2023-06-26 11:44:482023-06-26 11:44:49

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:44:49]
  • 评测
  • [2023-06-26 11:44:48]
  • 提交

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(i)){
				printf("! %d\n",i);
				fflush(stdout);
				return 0;
			}else leaf.pop_back();
		}
	}
	
	/*
	findFakeRoot();
	dfs(fr,0);
	int l=0,r=maxdep;
	while(l<r){
		int m=(l+r+1)/2;
		vector<int> v;
		for(int i=1;i<=n;i++){
			if(dep[i]>=m)v.pb(i);
		}
		if(query(v))l=m;
		else r=m-1;
	}
	if(l==0){
		printf("! %d\n",fr);
		fflush(stdout);
		return 0;
	}
	vector<int> v,perm;
	for(int i=1;i<=n;i++)if(dep[i]==l)v.pb(i);
	if(SZ(v)==1){
		printf("! %d\n",v[0]);
		fflush(stdout);
		return 0;
	}
	while(SZ(v)>2){
		int m=(SZ(v)+1)/2;
		vector<int> q;
		for(int i=0;i<m;i++){
			q.pb(v[i]);
		}
		for(int i:perm)q.pb(i);
		if(query(q)){
			for(int i=m;i<SZ(v);i++)perm.pb(v[i]);
			while(SZ(v)>m)v.pop_back();
		}else{
			for(int i=0;i<m;i++)perm.pb(v[i]);
			vector<int> tmp;
			for(int i=m;i<SZ(v);i++)tmp.pb(v[i]);
			v.clear();
			for(int i:tmp)v.pb(i);
		}
	}
	if(l==maxdep){
		vector<int> lf;
		int ans=v[0];
		for(int i:leaf){
			if(i!=v[0]&&i!=v[1])lf.pb(i);
		}
		lf.pb(v[0]);
		if(query(lf)){
			ans=v[0];
		}else ans=v[1];
		printf("! %d\n",ans);
		fflush(stdout);
		return 0;
	}
	vector<int> l0=getOtherLeaves(v[0]);
	vector<int> l1=getOtherLeaves(v[1]);
	int ans=v[0];
	if(SZ(l0)>=2){
		l0.pb(v[0]);
		if(query(l0)){
			ans=v[0];
		}else{
			ans=v[1];
		}
	}else{
		l1.pb(v[1]);
		if(query(l1)){
			ans=v[1];
		}else{
			ans=v[0];
		}
	}
	printf("! %d\n",ans);
	fflush(stdout);
	*/
}

Details

answer.code: In function ‘int main()’:
answer.code:125:34: error: could not convert ‘i’ from ‘int’ to ‘std::vector<int>’
  125 |                         if(query(i)){
      |                                  ^
      |                                  |
      |                                  int
answer.code: In function ‘bool query(std::vector<int>)’:
answer.code:104:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  104 |         scanf("%s",str);
      |         ~~~~~^~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:110:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  110 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
answer.code:113:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  113 |                 scanf("%d%d",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~