QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722977 | #9459. Tree Equation | SkyMaths | AC ✓ | 96ms | 16588kb | C++20 | 3.5kb | 2024-11-07 20:47:03 | 2024-11-07 20:47:04 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,l,r) for (int i(l), i##end(r); i <= i##end; ++i)
#define per(i,r,l) for (int i(r), i##end(l); i >= i##end; --i)
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define uint unsigned int
#define eb emplace_back
#define File(filename) freopen(filename".in", "r", stdin), freopen(filename".out", "w", stdout)
using namespace std;
template <typename Tx> inline void read(Tx &x) {x = 0; bool f = 0; char ch = getchar(); while (ch < '0' || ch > '9') f ^= ch == '-', ch = getchar(); while (ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); if (f) x = -x;}
template <typename Tx, typename ...Ty> inline void read(Tx &x, Ty &...y) {read(x); read(y...);}
template <typename Tx> inline void owrite(Tx x) {if (x > 9) owrite(x / 10); putchar('0' + x % 10);}
template <typename Tx> inline void write(Tx x, char ch = '\n') {owrite(x < 0 ? (putchar('-'), -x) : x); putchar(ch);}
template <typename Tx> inline void cmax(Tx &x, Tx y) {if (x < y) x = y;}
template <typename Tx> inline void cmin(Tx &x, Tx y) {if (x > y) x = y;}
namespace Main {
const int N = 1e5 + 9;
mt19937 mtrnd(time(NULL));
ull mask;
ull shift(ull x) { return x ^= mask, x ^= x << 13, x ^= x >> 7, x ^= x << 17, x ^= mask, x;}
struct Tree {
vector <int> G[N];
int dep[N], siz[N];
ull hsh[N];
void dfs(int u) {
siz[u] = hsh[u] = 1;
for (int v : G[u]) {
dep[v] = dep[u] + 1;
dfs(v);
siz[u] += siz[v];
hsh[u] += shift(hsh[v]);
}
}
ull calc(int u, ull x) {
ull ans = x;
for (int v : G[u]) ans += shift(calc(v, x));
return ans;
}
void init(int n) {
rep (i, 1, n) vector <int> ().swap(G[i]);
rep (i, 1, n) {
int fa; read(fa);
G[fa].eb(i);
}
dfs(1);
}
void output(int u, int fa, int &tot) {
int id = ++tot;
write(fa, ' ');
for (int v : G[u]) output(v, id, tot);
}
} A, B, C;
int a, b, n;
void skymaths() {
mask = mtrnd() * mtrnd();
read(a, b, n);
A.init(a), B.init(b), C.init(n);
int mxa(0), mxb(0);
rep (i, 1, a) cmax(mxa, A.dep[i]);
rep (i, 1, b) cmax(mxb, B.dep[i]);
map <ull, int> visx, visy, rtx, rty;
// X, Y 肯定在 C 中出现过
rep (i, 1, n) {
if (a <= n / C.siz[i] && !visx[C.hsh[i]]) {
visx[C.hsh[i]] = 1;
rtx[A.calc(1, C.hsh[i])] = i;
}
}
rep (i, 1, n) {
if (b <= n / C.siz[i] && !visy[C.hsh[i]]) {
visy[C.hsh[i]] = 1;
rty[B.calc(1, C.hsh[i])] = i;
}
}
int flag = 0;
for (auto pr : rtx) {
// 判定当 X = subtree(C[pr.se]) 时可不可以
// 此时 hsh(A · X) = pr.fi
ull val = pr.fi, val_by = C.hsh[1] + 1 - val;
if (rty.count(val_by)) {
int rx = pr.se, ry = rty[val_by];
write(C.siz[rx], ' ');
write(C.siz[ry], '\n');
int tot1(0), tot2(0);
C.output(rx, 0, tot1); putchar('\n');
C.output(ry, 0, tot2); putchar('\n');
flag = 1; break;
}
}
if (!flag) {
printf("Impossible\n");
}
}
/*
code from Purslane
thx
*/
signed main() {
// freopen("a.in", "r", stdin);
int T = 1;
read(T);
while (T--) {
skymaths();
}
return 0;
} } signed main() { Main::main(); return 0;}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 15400kb
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: 96ms
memory: 16588kb
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 2 8 0 1 0 1 1 3 3 3 1 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: 3ms
memory: 14304kb
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