QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#715377#9459. Tree EquationYansuan_HClAC ✓112ms22788kbC++143.8kb2024-11-06 11:41:032024-11-06 11:41:04

Judging History

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

  • [2024-11-06 11:41:04]
  • 评测
  • 测评结果:AC
  • 用时:112ms
  • 内存:22788kb
  • [2024-11-06 11:41:03]
  • 提交

answer

#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ull = unsigned long long;

#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { x = 0; char GC; bool f = 0;
	for (; !IC; GC) f |= c == '-';
	for (; IC; GC) x = x * 10 + c - 48;
	if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) { meow("AF@%d\n", __LINE__ ); exit(v); }

#define vc vector
#define eb emplace_back
#define pb push_back

const int N = 100005;
int A, B, C, ra, rb, rc;
vc<int> ga[N], gb[N], gc[N];
int fa[N], fb[N], fc[N];

using hsh = pair<int, ull>;
const hsh I {1, 1};
ull go(ull x) {
	ull y = (x << 32) >> 32, z = x >> 32;
	return (y * y * y + z * z * z) * 1453529 + 19260817;
}
hsh& operator += (hsh &l, const hsh &r) {
	l.first += r.first;
	l.second += go(r.second);
	return l;
}

hsh geth(int u, const auto &g) {
	hsh h = I;
	for (int v : g[u])
		h += geth(v, g);
	return h;
}
hsh gete(int u, hsh t, const auto &g) {
	hsh h = I; h.first += t.first; h.second += t.second;
	for (int v : g[u])
		h += gete(v, t, g);
	return h;
}

pair<int, int> dfs(int u, int d, const auto &g) {
	pair<int, int> cur(d, u);
	for (int v : g[u])
		cur = max(cur, dfs(v, d + 1, g));
	return cur;
}
int sic[N];
void dfs2(int u) {
	sic[u] = 1;
	for (int v : gc[u]) {
		dfs2(v);
		sic[u] += sic[v];
	}
}

pair<int, int> da, db; int d, p, px, py;

bool check() {
	U (i, 1, d - da.first) p = fc[p];
	px = p;
	vc<hsh> xs; hsh xtot {0, 0};
	for (int v : gc[p]) {
		hsh xi = geth(v, gc);
		xs.pb(xi);
		xtot += xi;
	}
	
	map<hsh, int> mp;
	for (int v : ga[ra]) {
		hsh ai = gete(v, xtot, ga);
		++mp[ai];
	}
	for (hsh xi : xs)
		++mp[xi];
	
	bool tag[C + 1] {};
	for (int v : gc[rc]) {
		hsh ci = geth(v, gc);
		--mp[ci];
		if (mp[ci] < 0)
			tag[v] = 1;
	}
	for (auto [h, cnt] : mp) if (cnt > 0)
		return 0;
	
	pair<int, int> dx = {0, 0};
	for (int v : gc[rc]) if (tag[v]) {
		dx = max(dfs(v, 1, gc), dx);
	}
	tie(d, p) = dx;
	U (i, 1, d - db.first) p = fc[p];
	py = p;
	vc<hsh> ys; hsh ytot {0, 0};
	for (int v : gc[p]) {
		hsh yi = geth(v, gc);
		ys.pb(yi);
		ytot += yi;
	}
	
	mp.clear();
	for (int v : gb[rb]) {
		hsh bi = gete(v, ytot, gb);
		++mp[bi];
	}
	for (hsh yi : ys) {
		++mp[yi];
	}
	
	for (int v : gc[rc]) if (tag[v]) {
		hsh ci = geth(v, gc);
		--mp[ci];
	}
	for (auto [h, cnt] : mp) if (cnt != 0)
		return 0;
	
	return 1;
}

int id;
void build(int u, int f) {
	int z = ++id;
	printf("%d ", f);
	for (int v : gc[u]) {
		build(v, z);
	}
}

void cons() {
	printf("%d %d\n", sic[px], sic[py]);
	
	id = 0;
	build(px, 0);
	puts("");
	
	id = 0;
	build(py, 0);
	puts("");
	
	id = 0;
}

void solve() {
	rd(A, B, C);
	U (i, 1, A) { rd(fa[i]); if (!fa[i]) ra = i; else ga[fa[i]].pb(i); }
	U (i, 1, B) { rd(fb[i]); if (!fb[i]) rb = i; else gb[fb[i]].pb(i); }
	U (i, 1, C) { rd(fc[i]); if (!fc[i]) rc = i; else gc[fc[i]].pb(i); }
	
	da = dfs(ra, 0, ga);
	db = dfs(rb, 0, gb);
	tie(d, p) = dfs(rc, 0, gc);
	dfs2(rc);
	
	// 1.
	bool f1 = check();
	if (f1) {
		cons();
		return;
	}
	
	swap(da, db);
	swap(A, B); swap(ra, rb);
	U (i, 1, max(A, B)) {
		swap(fa[i], fb[i]);
		swap(ga[i], gb[i]);
	}
	tie(d, p) = dfs(rc, 0, gc);
	bool f2 = check();
	if (f2) {
		swap(px, py);
		cons();
		return;
	}
	
	puts("Impossible");
}

void clear() {
	U (i, 1, A) ga[i].clear(), fa[i] = 0;
	U (i, 1, B) gb[i].clear(), fb[i] = 0;
	U (i, 1, C) gc[i].clear(), fc[i] = 0, sic[i] = 0;
	id = 0;
}

int main() {
//	freopen("ava.in", "r", stdin);
	
	int T; rd(T);
	while (T--) {
		solve();
		clear();
	}
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 112ms
memory: 22788kb

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 1 1 4 
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 ...

result:

ok 11122 cases passed

Test #3:

score: 0
Accepted
time: 0ms
memory: 11252kb

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