QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#725613 | #9459. Tree Equation | K8He | AC ✓ | 130ms | 12964kb | C++20 | 3.1kb | 2024-11-08 19:04:32 | 2024-11-08 19:04:32 |
Judging History
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,我给组数据试试?
詳細信息
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