QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#636842#9459. Tree Equationucup-team191#AC ✓380ms14164kbC++235.6kb2024-10-13 03:21:402024-10-13 03:21:40

Judging History

你现在查看的是测评时间为 2024-10-13 03:21:40 的历史记录

  • [2024-10-13 18:43:02]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果:AC
  • 用时:382ms
  • 内存:14224kb
  • [2024-10-13 10:44:25]
  • hack成功,自动添加数据
  • (/hack/952)
  • [2024-10-13 03:21:40]
  • 评测
  • 测评结果:100
  • 用时:380ms
  • 内存:14164kb
  • [2024-10-13 03:21:40]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
#define all(a) begin(a),end(a)
#define pb push_back

const int N=300010,MOD=1e9+7,MOD2=998244353;
const char en='\n';
const ll LLINF=1ll<<60;

inline int add(int A, int B, int M) {
	if(A + B >= M) return A + B - M;
	return A + B;
}

inline int mul(int A, int B, int M) {
	return (long long)A * B % M;
}

inline pii add(pii A, pii B)
{
	return {add(A.x,B.x,MOD),add(A.y,B.y,MOD2)};
}

inline pii mul(pii A, int B)
{
	return {mul(A.x,B,MOD),mul(A.y,B,MOD2)};
}

inline pii mul(pii A, pii B)
{
	return {mul(A.x,B.x,MOD),mul(A.y,B.y,MOD2)};
}

pii tree_hash(int x, vector < vi > &t, vector < bool > &zab, vector < pii > &gdje) {
	vector < pii > hsh_djece;
	for(int y : t[x]) if(!zab[y]) {
		hsh_djece.pb(tree_hash(y, t, zab, gdje));
	}
	int baza = 1e6 + 17 - (int)hsh_djece.size();
	sort(hsh_djece.begin(), hsh_djece.end());
	pii ret = {baza,baza};
	pii sad = {baza,baza};
	for(pii x : hsh_djece) {
		ret = add(ret, mul(x, sad));
		sad = mul(sad, baza);
	}
	return gdje[x] = ret;
}

int t,na,nb,nc;

vi getPars(const vector<vi>&x)
{
	int a=x.size();
	vi pars(a);
	pars[0]=-1;
	for (int i=0;i<a;++i) for (auto b: x[i]) pars[b]=i;
	return pars;
}

vector<vi> getMul(const vector<vi>&a,const vector<vi>&b)
{
	vi ap=getPars(a),bp=getPars(b);
	int as=a.size(),bs=b.size();
	assert(as*1ll*bs<=nc);
	vector<vi> nov(as*bs);
	for (int va=0;va<as;++va) for (int vb=0;vb<bs;++vb)
	{
		int x=va*bs+vb;
		if (x)
		{
			int p;
			if (vb==0) p=ap[va]*bs;
			else p=va*bs+bp[vb];
			nov[p].pb(x);
		}
	}
	return nov;
}

int ss[N];

void dfs1(int i,const vector<vi>&v)
{
	ss[i]=1;
	for (auto x: v[i])
	{
		dfs1(x,v);
		ss[i]+=ss[x];
	}
}

vi ord;
int ind[N];

void getSub(int i,const vector<vi>&v)
{
	ind[i]=ord.size();
	ord.pb(i);
	for (auto x: v[i]) getSub(x,v);
}

vector<vi> extractSub(int i,vector<vi>&v)
{
	ord.clear();
	getSub(i,v);
	int os=ord.size();
	vector<vi> re(os);
	for (auto x: ord) for (auto y: v[x])
	{
		//cout<<"extracting "<<x<<"->"<<y<<": "<<ind[x]<<"->"<<ind[y]<<endl;
		re[ind[x]].pb(ind[y]);
	}
	return re;
}

bool solve(vector<vi>&cha,vector<vi>&chb,vector<vi>&chc,int maxc,int kak,bool flip)
{
	vector<bool> zab(nc);
	vector<pii> gdje(nc);
	tree_hash(0,chc,zab,gdje);
	for (int vx=1;vx<=maxc;++vx) if (maxc%vx==0)
	{
		if (vx*1ll*na>=nc) continue;
		if ((nc+1-vx*1ll*na)%nb) continue;
		ord.clear();
		getSub(kak,chc);
		int cd=0;
		vi koj;
		for (auto x: ord) if (ss[x]%vx==0) ++cd,koj.pb(x);
		if (cd!=maxc/vx) continue;
		if (ss[koj.back()]!=vx) continue;
		vector<vi> xst=extractSub(koj.back(),chc);
		//cout<<"extracted size "<<vx<<endl;
		for (auto s: cha[0])
		{
			vector<vi> vca=extractSub(s,cha);
			//cout<<"extracted "<<vca.size()<<"("<<s<<" from a)"<<endl;
			/*cout<<"vca="<<en;
			for (auto x: vca)
			{
				for (auto y: x) cout<<y<<' ';
				cout<<en;
			}
			cout<<"xst="<<en;
			for (auto x: xst)
			{
				for (auto y: x) cout<<y<<' ';
				cout<<en;
			}
			cout<<endl;*/
			vector<vi> mnozi=getMul(vca,xst);
			//cout<<"mnozio"<<endl;
			vector<pii> ng(mnozi.size());
			vector<bool> nz(mnozi.size());
			//cout<<"mnozio "<<vca.size()<<' '<<xst.size()<<endl;
			if (gdje[kak]!=tree_hash(0,mnozi,nz,ng)) continue;
			//cout<<"uspjeh!"<<endl;
			multiset<pii> zamaknut;
			for (auto s1: cha[0])
			{
				vca=extractSub(s1,cha);
				mnozi=getMul(vca,xst);
				ng=vector<pii>(mnozi.size());
				nz=vector<bool>(mnozi.size());
				zamaknut.insert(tree_hash(0,mnozi,nz,ng));
			}
			for (auto x: xst[0])
			{
				vector<vi> sta=extractSub(x,xst);
				ng=vector<pii>(sta.size());
				nz=vector<bool>(sta.size());
				zamaknut.insert(tree_hash(0,sta,nz,ng));
			}
			ng=vector<pii>(nc);
			nz=vector<bool>(nc);
			int ns=nc;
			for (auto x: chc[0]) if (zamaknut.find(gdje[x])!=zamaknut.end())
			{
				zamaknut.erase(zamaknut.find(gdje[x]));
				nz[x]=1;
				ns-=ss[x];
			}
			if (zamaknut.size()) break;
			if (ns%nb) break;
			//cout<<"vx="<<vx<<endl;
			int vy=ns/nb;
			int zad=-1;
			for (int i=0;i<nc;++i)
			{
				if (nz[i]) for (auto x: chc[i]) nz[x]=1;
				else
				{
					if (ss[i]%vy==0) zad=i;
				}
			}
			if (zad==-1 || ss[zad]!=vy) break;
			vector<vi> yst=extractSub(zad,chc);
			vector<vi> mnoz2=getMul(chb,yst);
			auto h1=tree_hash(0,chc,nz,ng);
			vector<bool> nnz(mnoz2.size());
			vector<pii> nng(mnoz2.size());
			auto h2=tree_hash(0,mnoz2,nnz,nng);
			if (h1!=h2) break;
			vi parsx=getPars(xst),parsy=getPars(yst);
			if (flip) swap(parsx,parsy);
			int sx=parsx.size(),sy=parsy.size();
			cout<<sx<<' '<<sy<<endl;
			for (int i=0;i<sx-1;++i) cout<<parsx[i]+1<<' ';
			cout<<parsx.back()+1<<endl;
			for (int i=0;i<sy-1;++i) cout<<parsy[i]+1<<' ';
			cout<<parsy.back()+1<<endl;
			return 1;
		}
	}
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>na>>nb>>nc;
		vector<vi> cha(na),chb(nb),chc(nc);
		for (int i=0;i<na;++i)
		{
			int x;
			cin>>x;
			if (i) cha[x-1].pb(i);
		}
		for (int i=0;i<nb;++i)
		{
			int x;
			cin>>x;
			if (i) chb[x-1].pb(i);
		}
		for (int i=0;i<nc;++i)
		{
			int x;
			cin>>x;
			if (i) chc[x-1].pb(i);
		}
		dfs1(0,chc);
		int maxc=-1,kak=-1;
		for (auto x: chc[0]) if (ss[x]>maxc)
		{
			maxc=ss[x];
			kak=x;
		}
		if (solve(cha,chb,chc,maxc,kak,0)) continue;
		swap(na,nb);
		swap(cha,chb);
		if (solve(cha,chb,chc,maxc,kak,1)) continue;
		cout<<"Impossible"<<en;
		
		//cout<<"done"<<endl;
	}
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5564kb

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: 380ms
memory: 14164kb

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
8 2
0 1 1 3 3 3 1 1
0 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
5 1
0 1 1 1 1
0
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: 0ms
memory: 3668kb

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