QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#634093#9459. Tree Equationucup-team5052#AC ✓128ms32896kbC++173.9kb2024-10-12 16:41:372024-10-13 18:42:30

Judging History

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

  • [2024-10-13 18:42:30]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果：AC
  • 用时：128ms
  • 内存：32896kb
查看
  • [2024-10-13 10:44:25]
  • hack成功，自动添加数据
  • (/hack/952)
  • [2024-10-12 16:41:38]
  • 评测
  • 测评结果：100
  • 用时：135ms
  • 内存：32832kb
查看
  • [2024-10-12 16:41:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
int a[100010],b[100010],c[100010],id[100010],x[100010],y[100010],da[100010],db[100010],sa[100010],sb[100010],sc[100010],que[100010];
ull ha[100010],hb[100010],hc[100010],h[100010];
vector<int> va,vb;
vector<pair<ull,int>> ax,by;
mt19937 rnd;
struct Hash
{
	static constexpr int M=1e7+19;
	int head[10000020],nxt[100010],tot=0;
	ull val[100010];
	void insert(ull x)
	{
		int y=x%M;
		for(int i=head[y];i;i=nxt[i])
			if(val[i]==x) return;
		nxt[++tot]=head[y];
		val[tot]=x;
		head[y]=tot;
	}
	bool find(ull x)
	{
		int y=x%M;
		for(int i=head[y];i;i=nxt[i])
			if(val[i]==x) return true;
		return false;
	}
	void clear()
	{
		for(int i=1;i<=tot;i++) head[val[i]%M]=0;
		tot=0;
	}
}hs,hs2;
ull mix(ull x)
{
	x^=x<<23;
	x^=x>>7;
	x^=x<<17;
	return x;
}
ull hash64(ull x)
{
	return mix(mix(x)*18492746950827547);
}
int main() {
	std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T,na,nb,nc;
	cin>>T;
	while(T--)
	{
		cin>>na>>nb>>nc;
		for(int i=1;i<=na;i++) cin>>a[i],da[a[i]]++;
		for(int i=1;i<=nb;i++) cin>>b[i],db[b[i]]++;
		for(int i=1;i<=nc;i++) cin>>c[i];
		fill(sa+1,sa+na+1,1);
		fill(sb+1,sb+nb+1,1);
		fill(sc+1,sc+nc+1,1);
		fill(ha+1,ha+na+1,1);
		fill(hb+1,hb+nb+1,1);
		fill(hc+1,hc+nc+1,1);
		for(int i=na;i>1;i--)
		{
			sa[a[i]]+=sa[i];
			ha[a[i]]+=hash64(ha[i]);
		}
		for(int i=nb;i>1;i--)
		{
			sb[b[i]]+=sb[i];
			hb[b[i]]+=hash64(hb[i]);
		}
		for(int i=nc;i>1;i--)
		{
			sc[c[i]]+=sc[i];
			hc[c[i]]+=hash64(hc[i]);
		}
		for(int i=2;i<=nc;i++) hs.insert(hc[i]);
		int l=0,r=0;
		for(int i=1;i<=na;i++)
			if(da[i]==0) que[r++]=i;
		while(l<r)
		{
			swap(que[l],que[uniform_int_distribution<int>(l,r-1)(rnd)]);
			int u=que[l++];
			va.push_back(u);
			if((--da[a[u]])==0) que[r++]=a[u];
		}
		l=r=0;
		for(int i=1;i<=nb;i++)
			if(db[i]==0) que[r++]=i;
		while(l<r)
		{
			swap(que[l],que[uniform_int_distribution<int>(l,r-1)(rnd)]);
			int u=que[l++];
			vb.push_back(u);
			if((--db[b[u]])==0) que[r++]=b[u];
		}
		for(int i=1;i<=nc;i++)
		{
			if((ull)na*sc[i]>=nc) continue;
			ull x=hc[i];
			if(hs2.find(x)) continue;
			hs2.insert(x);
			bool ok=1;
			for(int u:va)
			{
				h[u]+=x;
				if(u==1) break;
				if(!hs.find(h[u]))
				{
					h[u]=0;
					for(int v:va)
					{
						h[v]=h[a[v]]=0;
						if(u==v) break;
					}
					ok=0;
					break;
				}
				h[a[u]]+=hash64(h[u]);
			}
			if(ok)
			{
				ax.emplace_back(h[1],i);
				fill(h+1,h+na+1,0);
			}
		}
		hs2.clear();
		for(int i=1;i<=nc;i++)
		{
			if((ull)nb*sc[i]>=nc) continue;
			ull x=hc[i];
			if(hs2.find(x)) continue;
			hs2.insert(x);
			bool ok=1;
			for(int u:vb)
			{
				h[u]+=x;
				if(u==1) break;
				if(!hs.find(h[u]))
				{
					h[u]=0;
					for(int v:vb)
					{
						h[v]=h[b[v]]=0;
						if(u==v) break;
					}
					ok=0;
					break;
				}
				h[b[u]]+=hash64(h[u]);
			}
			if(ok)
			{
				by.emplace_back(h[1],i);
				fill(h+1,h+nb+1,0);
			}
		}
		hs2.clear();
		sort(ax.begin(),ax.end());
		sort(by.begin(),by.end());
		bool ok=0;
		for(auto [h1,u]:ax)
		{
			auto it=lower_bound(by.begin(),by.end(),pair<ull,int>{hc[1]-h1+1,0});
			if(it==by.end()) continue;
			auto [h2,v]=*it;
			if(h1+h2-1!=hc[1]) continue;
			ok=1;
			int nx=1,ny=1;
			x[id[u]=1]=0;
			for(int i=1;i<=nc;i++)
				if(id[c[i]])
					x[id[i]=++nx]=id[c[i]];
			fill(id+1,id+nc+1,0);
			y[id[v]=1]=0;
			for(int i=1;i<=nc;i++)
				if(id[c[i]])
					y[id[i]=++ny]=id[c[i]];
			fill(id+1,id+nc+1,0);
			cout<<nx<<" "<<ny<<"\n";
			for(int i=1;i<=nx;i++) cout<<x[i]<<" \n"[i==nx];
			for(int i=1;i<=ny;i++) cout<<y[i]<<" \n"[i==ny];
			break;
		}
		if(!ok) cout<<"Impossible\n";
		fill(da+1,da+na+1,0);
		fill(db+1,db+nb+1,0);
		va.clear();vb.clear();
		ax.clear();by.clear();
		hs.clear();
	}
	return 0;
}
源文件, 语言: C++17

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 13912kb

input:

2
2 3 10
0 1
0 1 2
0 1 1 3 4 3 6 3 1 9
4 3 10
0 1 2 2
0 1 2
0 1 1 3 4 3 6 3 1 9

output:

Impossible
2 1
0 1
0

result:

ok 2 cases passed

Test #2:

score: 0
Accepted
time: 128ms
memory: 32896kb

input:

11122
3 3 11
0 1 1
0 1 1
0 1 1 1 4 4 1 1 8 8 1
7 2 10
0 1 2 2 2 1 1
0 1
0 1 2 1 1 5 5 5 1 1
7 8 14
0 1 2 1 1 1 1
0 1 2 1 1 1 1 1
0 1 1 3 1 1 1 1 1 1 1 11 1 1
4 8 11
0 1 1 1
0 1 1 1 1 1 6 6
0 1 1 1 1 1 6 6 1 1 1
3 4 13
0 1 1
0 1 1 1
0 1 1 3 1 5 1 1 8 1 10 1 12
11 2 14
0 1 2 1 4 4 4 1 1 1 1
0 1
0 1 1 ...

output:

3 1
0 1 1
0
1 2
0
0 1
1 1
0
0
1 1
0
0
2 2
0 1
0 1
1 2
0
0 1
1 5
0
0 1 2 1 1
1 1
0
0
2 8
0 1
0 1 1 3 3 3 1 1
1 1
0
0
4 1
0 1 1 1
0
3 1
0 1 1
0
5 1
0 1 2 1 1
0
1 1
0
0
1 1
0
0
1 1
0
0
1 1
0
0
2 1
0 1
0
1 5
0
0 1 1 1 1
1 1
0
0
1 3
0
0 1 1
1 2
0
0 1
3 1
0 1 1
0
1 4
0
0 1 1 1
1 4
0
0 1 1 1
1 2
0
0 1
1 3
...

result:

ok 11122 cases passed

Test #3:

score: 0
Accepted
time: 3ms
memory: 16036kb

input:

1
5 5 49
0 1 1 3 1
0 1 2 1 2
0 1 2 3 4 1 6 7 8 9 1 11 12 13 14 11 16 17 18 19 1 21 22 23 24 1 26 26 1 1 30 31 31 30 30 35 36 36 35 30 40 41 41 40 1 45 46 46 45

output:

5 5
0 1 2 3 4
0 1 2 2 1

result:

ok 1 cases passed

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2025-02-01 20:48:48 | 开源项目