QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725613#9459. Tree EquationK8HeAC ✓130ms12964kbC++203.1kb2024-11-08 19:04:322024-11-08 19:04:32

Judging History

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

  • [2024-11-08 19:04:32]
  • 评测
  • 测评结果:AC
  • 用时:130ms
  • 内存:12964kb
  • [2024-11-08 19:04:32]
  • 提交

answer

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef unsigned long long ull;
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
const int N = 1e5 + 10, P = 998244353;
namespace IO {
	int rnt () {
		int x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
}
namespace SOLVE {
	using namespace IO;	
	ull mask = std::chrono::system_clock::now().time_since_epoch().count();
	int na, nb, nc, siz[N]; ull F[N];
	std::vector <int> A[N], B[N], C[N];
	std::map <ull, ull> visa, visb, cntc, U;
	std::vector <int> X, Y;
	ull Hash (ull val) {
		val ^= mask;
		val ^= val << 13;
		val ^= val >> 7;
		val ^= val << 17;
		val ^= mask;
		return val;
	}
	void DFSC (int u) {
		siz[u] = 1, F[u] = 0;
		far (v, C[u])
			DFSC (v), siz[u] += siz[v];
		std::sort (C[u].begin (), C[u].end (), [&] (int x, int y) -> bool { return siz[x] < siz[y]; });
		far (v, C[u])
			++cntc[F[u] += Hash (F[v])];
		U[F[u]] = u, ++cntc[0];
		return;
	}
	ull DFSA (int u, ull w) { ull S = w; far (v, A[u]) S += Hash (DFSA (v, w)); return S; }
	ull DFSB (int u, ull w) { ull S = w; far (v, B[u]) S += Hash (DFSB (v, w)); return S; }
	void GetX (int u, int fa) { X.emplace_back (fa); int i = X.size (); far (v, C[u]) GetX (v, i); return; }
	void GetY (int u, int fa) { Y.emplace_back (fa); int i = Y.size (); far (v, C[u]) GetY (v, i); return; }
	void In () {
		na = rnt (), nb = rnt (), nc = rnt ();
		_for (i, 1, na) A[rnt ()].emplace_back (i);
		_for (i, 1, nb) B[rnt ()].emplace_back (i);
		_for (i, 1, nc) C[rnt ()].emplace_back (i);
		return;
	}
	void Solve () {
		DFSC (C[0][0]);
		far (p, cntc) {
			if (p.second >= na - 1) visa[DFSA (A[0][0], p.first)] = p.first;
			if (p.second >= nb - 1) visb[DFSB (B[0][0], p.first)] = p.first;
		}
		far (p, visa) {
			ull AX = p.first, BY = F[1] - AX;
			if (visb.count (BY)) {
				ull hX = p.second, hY = visb[BY];
				GetX (U[hX], 0), GetY (U[hY], 0);
				break;
			}
		}
		return;
	}
	void Out () {
		if (X.empty ())
			puts ("Impossible");
		else {
			printf ("%d %d\n", (int)X.size (), (int)Y.size ());
			far (u, X) printf ("%d ", u);
			puts ("");
			far (u, Y) printf ("%d ", u);
			puts ("");
		}
		return;
	}
	void Clear () {
		_for (i, 0, na) std::vector <int> ().swap (A[i]);
		_for (i, 0, nb) std::vector <int> ().swap (B[i]);
		_for (i, 0, nc) std::vector <int> ().swap (C[i]);
		std::map <ull, ull> ().swap (visa);
		std::map <ull, ull> ().swap (visb);
		std::map <ull, ull> ().swap (cntc);
		std::map <ull, ull> ().swap (U);
		std::vector <int> ().swap (X);
		std::vector <int> ().swap (Y);
		return;
	}
}
int main () {
	int T = IO::rnt ();
	while (T--) {
		SOLVE::In ();
		SOLVE::Solve ();
		SOLVE::Out ();
		SOLVE::Clear ();
	}
	return 0;
} /*

*/

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5960kb

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: 130ms
memory: 12964kb

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

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 1 3 3 

result:

ok 1 cases passed

Extra Test:

score: 0
Extra Test Passed