QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#312157#5015. 树czcCompile Error//C++143.9kb2024-01-23 14:45:062024-01-23 14:45:06

Judging History

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

  • [2024-01-23 14:45:06]
  • 评测
  • [2024-01-23 14:45:06]
  • 提交

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: In function ‘void judger::init()’:
answer.code:32:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   32 |                 scanf("%d",&n);
      |                 ~~~~~^~~~~~~~~
answer.code:44:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   44 |                         scanf("%d%d",&u,&v);
      |                         ~~~~~^~~~~~~~~~~~~~
answer.code: In function ‘int main()’:
answer.code:187:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  187 |         freopen("czc.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cccJKBd6.o: in function `ask(int, std::vector<int, std::allocator<int> >)':
answer.code:(.text+0xd50): multiple definition of `ask(int, std::vector<int, std::allocator<int> >)'; /tmp/ccGxryz7.o:implementer.cpp:(.text+0xb60): first defined here
/usr/bin/ld: /tmp/cccJKBd6.o: in function `answer(int, int)':
answer.code:(.text+0x1970): multiple definition of `answer(int, int)'; /tmp/ccGxryz7.o:implementer.cpp:(.text+0x1260): first defined here
/usr/bin/ld: /tmp/cccJKBd6.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccGxryz7.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status