QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#634570#9459. Tree Equationucup-team052#AC ✓212ms23324kbC++144.2kb2024-10-12 17:38:162024-10-12 17:38:17

Judging History

你现在查看的是测评时间为 2024-10-12 17:38:17 的历史记录

  • [2024-10-13 18:42:33]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果:AC
  • 用时:168ms
  • 内存:23164kb
  • [2024-10-13 10:44:25]
  • hack成功,自动添加数据
  • (/hack/952)
  • [2024-10-12 17:38:17]
  • 评测
  • 测评结果:100
  • 用时:212ms
  • 内存:23324kb
  • [2024-10-12 17:38:16]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,na,nb,nc;
int fa[3][100005];

namespace solver{
	int n,m,sz,_out;
	vector <int> son[100005];
	int fa[4][100005],label[2][100005];
	ull h(ull x){
		return x * x * 127 + x * 114 + 514;
	}

	ull f(ull x){
		return h(x >> 30) + h(x & ((1u << 30) - 1));
	}

	int dep[100005],siz[100005],tag[100005];
	ull A[2][100005];
	__gnu_pbds::gp_hash_table <ull,int> buc;
	void dfs(int u){
		label[0][u] = ++sz;
		fa[2][sz] = label[0][fa[1][u]];
		for(int v:son[u]){
			if(tag[v]) continue;
			dfs(v);
		}
	}
	void dfs2(int u,int f){
		label[1][u] = ++_out;
		fa[3][_out] = label[1][f];
		for(int v:son[u]) dfs2(v,u);
	}
	int solve(){
		rep(u,1,m) son[u].clear();
		rep(u,2,m) son[fa[1][u]].eb(u);
/*		printf("try solve n=%d m=%d\n",n,m);
		rep(u,1,n) printf("%d ",fa[0][u]);
		printf("\n");
		rep(u,1,m) printf("%d ",fa[1][u]);
		printf("\n");*/
		int p = 1,d1 = 0,d2 = 0;
		rep(u,2,m){
			dep[u] = dep[fa[1][u]] + 1;
			if(dep[u] > dep[p]) p = u;
		}
		d1 = dep[p];
		fill(siz,siz + m + 1,1);
		fill(A[0],A[0] + m + 1,1);
		per(u,m,2){
			siz[fa[1][u]] += siz[u];
			A[0][fa[1][u]] += f(A[0][u]);
		}
		rep(u,2,n){
			dep[u] = dep[fa[0][u]] + 1;
			chkmax(d2,dep[u]);
		}
		d1 -= d2;
		if(d1 < 0) return 0;
		while(d1){
			p = fa[1][p];
			d1--;
		}
//		printf("p=%d\n",p);
		if(!p || 1ll * siz[p] * n > m) return 0;

		fill(A[1],A[1] + n + 1,A[0][p]);
		per(u,n,2) A[1][fa[0][u]] += f(A[1][u]);
		__gnu_pbds::gp_hash_table <ull,int> ovo;
		buc.swap(ovo);
		rep(u,2,n) if(fa[0][u] == 1) buc[A[1][u]]++;
		rep(u,1,m) if(fa[1][u] == p) buc[A[0][u]]++;

		fill(tag,tag + m + 1,0);
		rep(u,2,m){
			if(fa[1][u] == 1 && buc[A[0][u]]){
				tag[u] = 1;
//				printf("del %d\n",u);
				buc[A[0][u]]--;
			}
		}
		for(pair <ull,int> I:buc) if(I.second) return 0;
		sz = _out = 0;
		dfs(1);
		dfs2(p,0);
/*		printf("succ!\n");
		printf("sz=%d\n",sz);
		rep(u,1,sz) printf("%d ",fa[2][u]);
		printf("\n_out=%d\n",_out);
		rep(u,1,_out) printf("%d ",fa[3][u]);
		printf("\n");*/
		return 1;
	}	
}

int sz;
int temp[100005];
int check(int tp){
	solver::n = na;solver::m = nc;
	rep(u,1,na) solver::fa[0][u] = fa[0][u];
	rep(u,1,nc) solver::fa[1][u] = fa[2][u];
	if(!solver::solve()) return 0;
	solver::n = nb;solver::m = solver::sz;
	rep(u,1,nb) solver::fa[0][u] = fa[1][u];
	rep(u,1,solver::m) solver::fa[1][u] = solver::fa[2][u];
	sz = solver::_out;
	rep(u,1,sz) temp[u] = solver::fa[3][u];
	if(!solver::solve()) return 0;
	if(solver::sz != 1) return 0;
//	printf("[output]\n");
	if(!tp){
		printf("%d %d\n",sz,solver::_out);
		rep(u,1,sz) printf("%d%c",temp[u]," \n"[u == sz]);
		rep(u,1,solver::_out) printf("%d%c",solver::fa[3][u]," \n"[u == solver::_out]);
	}else{
		printf("%d %d\n",solver::_out,sz);	
		rep(u,1,solver::_out) printf("%d%c",solver::fa[3][u]," \n"[u == solver::_out]);
		rep(u,1,sz) printf("%d%c",temp[u]," \n"[u == sz]);
	}
	return 1;
}

void solve(){
	scanf("%d%d%d",&na,&nb,&nc);
	rep(u,1,na) scanf("%d",&fa[0][u]);
	rep(u,1,nb) scanf("%d",&fa[1][u]);
	rep(u,1,nc) scanf("%d",&fa[2][u]);
	if(check(0)) return;
	swap(na,nb);
	rep(u,1,max(na,nb)) swap(fa[0][u],fa[1][u]);
	if(check(1)) return;
	printf("Impossible\n");
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 212ms
memory: 23324kb

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: 3ms
memory: 12012kb

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