QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#847932#9459. Tree EquationyuanruiqiAC ✓143ms27788kbC++143.1kb2025-01-08 13:36:482025-01-08 13:36:49

Judging History

你现在查看的是最新测评结果

  • [2025-01-08 13:36:49]
  • 评测
  • 测评结果:AC
  • 用时:143ms
  • 内存:27788kb
  • [2025-01-08 13:36:48]
  • 提交

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