QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#847932 | #9459. Tree Equation | yuanruiqi | AC ✓ | 143ms | 27788kb | C++14 | 3.1kb | 2025-01-08 13:36:48 | 2025-01-08 13:36:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr int mod = 1000000000 + 33;
constexpr int base = 13331;
constexpr int maxn = 100000 + 10;
u64 shift(u64 x)
{
return (x << 13) ^ (x >> 19) ^ (x << 3);
}
struct tree
{
int p[maxn];
vector<int> g[maxn];
int n;
int d[maxn], s[maxn];
int init(int _n)
{
n = _n;
for (int i=0;i<=n;++i) g[i].clear();
for (int i=1;i<=n;++i) cin >> p[i], g[p[i]].emplace_back(i), d[i] = d[p[i]] + 1;
int mx = 0;
for (int i=1;i<=n;++i) mx = max(mx, d[i]);
memset(s, 0, sizeof(s[0]) * (n + 5));
for (int i=n;i>=1;--i) ++s[i], s[p[i]] += s[i];
return mx;
}
u64 h[maxn];
void get(const u64 w)
{
memset(h, 0, sizeof(h[0]) * (n + 5));
for (int i=n;i>=1;--i)
{
h[i] += w;
h[p[i]] += shift(h[i]);
}
}
int dfs(int u)
{
int p = u;
for (int v : g[u])
{
int w = dfs(v);
if (d[w] > d[p]) p = w;
}
return p;
}
int id[maxn];
void out(int u)
{
queue<int> q;
vector<int> w;
q.push(u);
while (q.size())
{
int u = q.front(); q.pop();
w.emplace_back(u);
for (int v : g[u]) q.push(v);
}
for (int i=0;i<w.size();++i) id[w[i]] = i + 1;
cout << "0 ";
for (int i=1;i<w.size();++i) cout << id[p[w[i]]] << ' ';
cout << '\n';
}
} ta, tb, tc;
int tag[maxn];
void solve()
{
int na, nb, nc;
cin >> na >> nb >> nc;
int ma = ta.init(na);
int mb = tb.init(nb);
int mc = tc.init(nc);
int m = 0;
for (int i=1;i<=nc;++i) if (tc.d[i] == mc) m = i;
tc.get(1);
auto run = [&](tree &ta, tree& tb, int p)
{
int x = m;
while (tc.d[x] > ma) x = tc.p[x];
if (tc.d[x] != ma) return 0;
ta.get(tc.h[x]);
map<u64, int> mp;
for (int v : ta.g[1]) ++mp[ta.h[v]];
for (int v : tc.g[x]) ++mp[tc.h[v]];
int y = 1;
for (int v : tc.g[1])
{
if (mp[tc.h[v]] > 0) --mp[tc.h[v]];
else
{
int z = tc.dfs(v);
if (tc.d[z] > tc.d[y]) y = z;
}
}
int s = 0;
for (auto [x, y] : mp) s += y;
if (s) return 0;
while (tc.d[y] > mb) y = tc.p[y];
if (tc.d[y] != mb) return 0;
tb.get(tc.h[y]);
if (ta.h[1] + tb.h[1] - 1 == tc.h[1])
{
if (p) swap(x, y);
cout << tc.s[x] << ' ' << tc.s[y] << '\n';
tc.out(x);
tc.out(y);
return 1;
}
return 0;
};
if (run(ta, tb, 0)) return;
swap(na, nb); swap(ma, mb);
if (run(tb, ta, 1)) return;
cout << "Impossible\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16276kb
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: 143ms
memory: 27788kb
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 1 1 3 3 3 0 1 1 1 0 0 4 1 0 1 1 1 0 3 1 0 1 1 0 5 1 0 1 1 1 2 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: 16084kb
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 2 2
result:
ok 1 cases passed
Extra Test:
score: 0
Extra Test Passed