QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#715377 | #9459. Tree Equation | Yansuan_HCl | AC ✓ | 112ms | 22788kb | C++14 | 3.8kb | 2024-11-06 11:41:03 | 2024-11-06 11:41:04 |
Judging History
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,我给组数据试试?
詳細信息
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