QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#115557 | #4926. Where Is the Root? | jamielim | Compile Error | / | / | C++14 | 3.6kb | 2023-06-26 11:44:48 | 2023-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]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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); | ~~~~~^~~~~~~~~~~~~~