QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#720728#9459. Tree EquationforgotmyhandleAC ✓427ms30036kbC++142.8kb2024-11-07 13:49:442024-11-07 13:49:45

Judging History

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

  • [2024-11-07 13:49:45]
  • 评测
  • 测评结果:AC
  • 用时:427ms
  • 内存:30036kb
  • [2024-11-07 13:49:44]
  • 提交

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