QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#720728 | #9459. Tree Equation | forgotmyhandle | AC ✓ | 427ms | 30036kb | C++14 | 2.8kb | 2024-11-07 13:49:44 | 2024-11-07 13:49:45 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int a, b, c;
vector<int> A[200005], B[200005], C[200005];
int sz[200005];
unsigned long long H[200005];
inline unsigned long long f(unsigned long long x) { return 3225 * x * x * x + 3653 * x * x + 3929; }
inline unsigned long long F(unsigned long long x) { return f(x & ((1ull << 31) - 1)) + f(x >> 31); }
map<unsigned long long, int> mp;
map<unsigned long long, unsigned long long> mp1, mp2;
void dfs1(int x) {
sz[x] = 1 + (H[x] = 0);
for (auto v : C[x]) {
dfs1(v);
sz[x] += sz[v];
}
sort(C[x].begin(), C[x].end(), [](int a, int b) { return sz[a] < sz[b]; });
++mp[0];
for (auto v : C[x]) {
H[x] += F(H[v]);
++mp[H[x]];
}
}
unsigned long long dfs2(int x, unsigned long long w) {
unsigned long long ret = w;
for (auto v : A[x]) ret += F(dfs2(v, w));
return ret;
}
unsigned long long dfs3(int x, unsigned long long w) {
unsigned long long ret = w;
for (auto v : B[x]) ret += F(dfs3(v, w));
return ret;
}
int ncnt;
void dfs4(int x, int fa) { cout << fa << " "; int id = ++ncnt; for (auto v : C[x]) dfs4(v, id); }
int main() {
// freopen("x.in", "r", stdin);
// freopen("x.out", "w", stdout);
int tc;
cin >> tc;
while (tc--) {
mp.clear();
mp1.clear();
mp2.clear();
cin >> a >> b >> c;
for (int i = 0; i <= a; i++) A[i].clear();
for (int i = 0; i <= b; i++) B[i].clear();
for (int i = 0; i <= c; i++) C[i].clear();
for (int i = 1, x; i <= a; i++) cin >> x, A[x].emplace_back(i);
for (int i = 1, x; i <= b; i++) cin >> x, B[x].emplace_back(i);
for (int i = 1, x; i <= c; i++) cin >> x, C[x].emplace_back(i);
dfs1(C[0][0]);
for (auto v : mp) {
unsigned long long w = v.first;
if (v.second >= a - 1)
mp1[dfs2(A[0][0], w)] = w;
if (v.second >= b - 1)
mp2[dfs3(B[0][0], w)] = w;
}
bool ok = 0;
for (auto v : mp1) {
unsigned long long hx = v.first, hy = H[C[0][0]] - hx;
if (mp2.count(hy)) {
hx = v.second, hy = mp2[hy];
int rx = c, ry = c;
for (int i = 1; i <= c; i++) {
if (H[i] == hx)
rx = i;
if (H[i] == hy)
ry = i;
}
cout << sz[rx] << " " << sz[ry] << "\n";
ncnt = 0, dfs4(rx, 0), cout << "\n";
ncnt = 0, dfs4(ry, 0), cout << "\n";
ok = 1;
break;
}
}
if (!ok)
cout << "Impossible\n";
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 19212kb
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: 427ms
memory: 30036kb
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:
1 3 0 0 1 1 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 1 5 0 0 1 1 1 1 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: 5ms
memory: 18972kb
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