QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #312158 | #5015. 树 | czc | Compile Error | / | / | C++14 | 4.1kb | 2024-01-23 14:45:43 | 2024-01-23 14:45:44 |
Judging History
answer
#include<bits/stdc++.h>
#include"tree.h"
//#define rb(a,b,c) for(int a=(b);a<=(c);++a)
//#define rl(a,b,c) for(int a=(b);a>=(c);--a)
//#define rep(a,b) for(int a=0;a<(b);++a)
//#define LL long long
//#define II(a,b) make_pair(a,b)
//#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
//#define random(a) rng()%a
//#define ALL(a) a.begin(),a.end()
//#define check_min(a,b) a=min(a,b)
//#define check_max(a,b) a=max(a,b)
//using namespace std;
//const int INF=0x3f3f3f3f;
//typedef pair<int,int> mp;
//namespace judger
//{
// const int N=1005;
// int n,d[N][N],f[N],c1,c2,A,B;
// vector<int>e[N];
// multiset<pair<int,int>>s,t;
// int fa(int x){return x==f[x]?x:f[x]=fa(f[x]);}
// void dfs(int u,int f,int b,int w)
// {
// d[b][u]=w;
// for(auto v:e[u])
// if(v!=f)
// dfs(v,u,b,w+1);
// }
// void init()
// {
// scanf("%d",&n);
// cin>>A>>B;
// if(n<1||n>1000)
// {
// puts("Invalid n");
// exit(0);
// }
// for(int i=1;i<=n;i++)
// f[i]=i;
// for(int i=1;i<n;i++)
// {
// int u,v;
// scanf("%d%d",&u,&v);
// if(u<1||u>n||v<1||v>n||fa(u)==fa(v))
// {
// cerr<<u<<" "<<v<<endl;
// puts("Invalid edge");
// exit(0);
// }
// if(u>v) swap(u,v);
// s.insert({u,v});
// e[u].push_back(v);
// e[v].push_back(u);
// f[fa(u)]=fa(v);
// }
// for(int i=1;i<=n;i++)
// dfs(i,0,i,0);
// }
// int ask(int u,vector<int>v)
// {
// c1++;
// c2+=v.size();
// if(c1>A)
// {
// puts("Too many queries");
// exit(0);
// }
// if(c2>B)
// {
// puts("The sum is too large");
// exit(0);
// }
// if(u<1||u>n)
// {
// puts("Invalid ask");
// exit(0);
// }
// sort(v.begin(),v.end());
// for(int i=1;i<v.size();i++)
// {
// if(v[i]==v[i-1])
// {
// puts("Invalid ask");
// exit(0);
// }
// }
// int s=0;
// for(auto i:v)
// {
// if(i<1||i>n)
// {
// puts("Invalid ask");
// exit(0);
// }
// s+=d[u][i];
// }
// return s;
// }
// void answer(int u,int v)
// {
// if(u>v) swap(u,v);
// if(t.size()==n-1){
// puts("Different tree");
// exit(0);
// }
// if(t.count(II(u,v))){
// puts("Different tree");
// exit(0);
// }
// t.insert({u,v});
// }
// void chk()
// {
// if(s==t)
// puts("Correct"),cout<<"cnt="<<c1<<' '<<"sum="<<c2<<endl;
// else
// puts("Different tree");
// }
//}
//int ask(int u,std::vector<int>v) {return judger::ask(u,v);}
//void answer(int u,int v) {judger::answer(u,v);}
const int maxn=1005;
vector<int> V[maxn],V2[maxn];
vector<int> G[maxn];
int Fa[maxn];
void solve(int l,int r,int fa,int dep){
vector<int> now;
for(int i=l;i<=r;i++) now.push_back(V[dep][i]);
int sum=ask(fa,now);
int sum2=ask(Fa[fa],now);
int delta=sum2-sum;
int x=(delta+r-l+1)/2;
if(!x) return ;
if(x==r-l+1){
for(int i=l;i<=r;i++){
Fa[V[dep][i]]=fa;
G[fa].push_back(V[dep][i]);
}
return ;
}
int mid=(l+r)>>1;
solve(l,mid,fa,dep);
solve(mid+1,r,fa,dep);
}
void solver(int n,int A,int B){
srand(time(0));
// if(n*(n-1)/2<=A){
// for(int i=1;i<=n;i++){
// for(int j=i+1;j<=n;j++){
// vector<int> now;
// now.push_back(j);
// if(ask(i,now)==1) answer(i,j);
// }
// }
// return ;
// }
int rt=rand()%n+1;
for(int i=1;i<=n;i++){
if(i==rt) continue;
vector<int> now;
now.push_back(i);
int dep=ask(rt,now);
V[dep].push_back(i);
V2[dep].push_back(i);
if(dep==1) G[rt].push_back(i),Fa[i]=rt;
}
for(int i=2;i<=n;i++){//对于每个dep分别找父亲
random_shuffle(V2[i-1].begin(),V2[i-1].end());
for(auto fa:V2[i-1]){
if(!V[i].size()) break;
random_shuffle(V[i].begin(),V[i].end());
solve(0,V[i].size()-1,fa,i);
for(auto x:G[fa]){
V[i].erase(find(V[i].begin(),V[i].end(),x));
}
}
}
for(int i=1;i<=n;i++){
for(auto y:G[i]){
answer(i,y);
}
}
}
//int main(){
// int st=clock();
// freopen("czc.txt","r",stdin);
// judger::init();
// solver(judger::n,judger::A,judger::B);
// judger::chk();
// cout<<clock()-st;
// return 0;
//}
詳細信息
implementer.cpp: In function ‘void regduj260135279::init()’:
implementer.cpp:32:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
32 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
implementer.cpp:45:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
45 | scanf("%d%d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~
answer.code:124:1: error: ‘vector’ does not name a type
124 | vector<int> V[maxn],V2[maxn];
| ^~~~~~
answer.code:125:1: error: ‘vector’ does not name a type
125 | vector<int> G[maxn];
| ^~~~~~
answer.code: In function ‘void solve(int, int, int, int)’:
answer.code:128:9: error: ‘vector’ was not declared in this scope; did you mean ‘std::vector’?
128 | vector<int> now;
| ^~~~~~
| std::vector
In file included from /usr/include/c++/13/vector:66,
from /usr/include/c++/13/queue:63,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:157,
from answer.code:1:
/usr/include/c++/13/bits/stl_vector.h:425:11: note: ‘std::vector’ declared here
425 | class vector : protected _Vector_base<_Tp, _Alloc>
| ^~~~~~
answer.code:128:16: error: expected primary-expression before ‘int’
128 | vector<int> now;
| ^~~
answer.code:129:31: error: ‘now’ was not declared in this scope; did you mean ‘pow’?
129 | for(int i=l;i<=r;i++) now.push_back(V[dep][i]);
| ^~~
| pow
answer.code:129:45: error: ‘V’ was not declared in this scope
129 | for(int i=l;i<=r;i++) now.push_back(V[dep][i]);
| ^
answer.code:130:24: error: ‘now’ was not declared in this scope; did you mean ‘pow’?
130 | int sum=ask(fa,now);
| ^~~
| pow
answer.code:137:28: error: ‘V’ was not declared in this scope
137 | Fa[V[dep][i]]=fa;
| ^
answer.code:138:25: error: ‘G’ was not declared in this scope
138 | G[fa].push_back(V[dep][i]);
| ^
answer.code: In function ‘void solver(int, int, int)’:
answer.code:161:17: error: ‘vector’ was not declared in this scope; did you mean ‘std::vector’?
161 | vector<int> now;
| ^~~~~~
| std::vector
/usr/include/c++/13/bits/stl_vector.h:425:11: note: ‘std::vector’ declared here
425 | class vector : protected _Vector_base<_Tp, _Alloc>
| ^~~~~~
answer.code:161:24: error: expected primary-expression before ‘int’
161 | vector<int> now;
| ^~~
answer.code:162:17: error: ‘now’ was not declared in this scope; did you mean ‘pow’?
162 | now.push_back(i);
| ^~~
| pow
answer.code:164:17: error: ‘V’ was not declared in this scope
164 | V[dep].push_back(i);
| ^
answer.code:165:17: error: ‘V2’ was not declared in this scope
165 | V2[dep].push_back(i);
| ^~
answer.code:166:28: error: ‘G’ was not declared in this scope
166 | if(dep==1) G[rt].push_back(i),Fa[i]=rt;
| ^
answer.code:169:32: error: ‘V2’ was not declared in this scope
169 | random_shuffle(V2[i-1].begin(),V2[i-1].end());
| ^~
answer.code:169:17: error: ‘random_shuffle’ was not declared in this scope; did you mean ‘std::random_shuffle’?
169 | random_shuffle(V2[i-1].begin(),V2[i-1].end());
| ^~~~~~~~~~~~~~
| std::random_shuffle
In file included from /usr/include/c++/13/algorithm:61,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/bits/stl_algo.h:4620:5: note: ‘std::random_shuffle’ declared here
4620 | random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
| ^~~~~~~~~~~~~~
answer.code:171:29: error: ‘V’ was not declared in this scope
171 | if(!V[i].size()) break;
| ^
answer.code:172:40: error: ‘V’ was not declared in this scope
172 | random_shuffle(V[i].begin(),V[i].end());
| ^
answer.code:174:36: error: ‘G’ was not declared in this scope
174 | for(auto x:G[fa]){
| ^
answer.code:175:44: error: ‘find’ was not declared in this scope; did you mean ‘std::find’?
175 | ...