QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#635752#9459. Tree Equationucup-team4906#AC ✓750ms22240kbC++203.1kb2024-10-12 20:51:242024-10-12 20:51:24

Judging History

你现在查看的是测评时间为 2024-10-12 20:51:24 的历史记录

  • [2024-10-13 18:42:44]
  • 管理员手动重测本题所有得分≥97分的提交记录
  • 测评结果:AC
  • 用时:667ms
  • 内存:21128kb
  • [2024-10-13 10:44:25]
  • hack成功,自动添加数据
  • (/hack/952)
  • [2024-10-12 20:51:24]
  • 评测
  • 测评结果:100
  • 用时:750ms
  • 内存:22240kb
  • [2024-10-12 20:51:24]
  • 提交

answer

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
const ull mask = std::chrono::steady_clock::now().time_since_epoch().count();

using namespace std;

#define N 100010

ull shift(ull x) {
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}
int na, nb, nc;
bool flag = 0;
vector<int>ea[N], eb[N], ec[N];
vector<int>D[N];
int sz[N];
ull hsh[N];
// ull get_hash(int u, int f) {
//     ull res = 1;
//     for(auto v : ed[u]) {
//         if(v == f) continue;
//         res += shift(get_hash(v, u));
//     }
//     return res;
// }

ull dfs(int u)
{
    ull res = 1; sz[u] = 1;
    for (int v : ec[u])
    {
        res += shift(dfs(v));
        sz[u] += sz[v];
    }
    D[sz[u]].push_back(u);
    // cout << "???"
    return hsh[u] = res;
}
void DFS(int u, int fid, int &n, vector<int>&a)
{
    ++ n; a.push_back(fid);
    int id = n;
    for (int v : ec[u]) DFS(v, id, n, a);
}
ull Aval(int u, ull w)
{
    ull res = w;
    for (int v : ea[u])
    {
        res += shift(Aval(v, w));
    }
    return res;
}
ull Bval(int u, ull w)
{
    ull res = w;
    for (int v : eb[u])
    {
        res += shift(Bval(v, w));
    }
    return res;
}
int ck(int u)
{
    int p = sz[u];
    // cout << "???:" << p << endl;
    if ((1LL * p * na > nc) || (nc + 1 - p * na) % nb) return -1;
    int q = (nc + 1 - p * na) / nb;

    // cout << "GG:" << p << ' ' << q << endl;
    for (int v : D[q])
    {
        // cout << "EEE:" << u << ' ' << v << Aval(1, hsh[u]) + Bval(1, hsh[v]) - 1 << ' ' << hsh[1] << endl;
        if (Aval(1, hsh[u]) + Bval(1, hsh[v]) - 1 == hsh[1])
        {
            return v;
        }
    }
    return -1;
}
void sol(int u)
{
    int v = ck(u);
    if (v != -1)
    {
       vector<int>A, B;
       int n1 = 0, n2 = 0;
       DFS(u, 0, n1, A); DFS(v, 0, n2, B);
       cout << n1 << ' ' << n2 << '\n';
       for (int x : A) {cout << x << ' ';} cout << '\n';
       for (int x : B) {cout << x << ' ';} cout << '\n';
       flag = 1; return ;
    }
    for (int v : ec[u])
    {
        sol(v);
        if (flag) return ;
    }
}
void sol()
{
    cin >> na >> nb >> nc;
    for (int i = 1; i <= na; i ++)
    {
        int x;
        cin >> x;
        if (x == 0)continue;
        else ea[x].push_back(i);
    }
    for (int i = 1; i <= nb; i ++)
    {
        int x;
        cin >> x;
        if (x == 0)continue;
        else eb[x].push_back(i);
    }
    for (int i = 1; i <= nc; i ++)
    {
        int x;
        cin >> x;
        if (x == 0)continue;
        else ec[x].push_back(i);
    }
    dfs(1);
    sol(1);

    if (!flag) {cout << "Impossible\n";}
    for (int i = 1; i <= nc; i ++)
    {
        ea[i].clear(), eb[i].clear(), ec[i].clear();
        D[i].clear(); hsh[i] = 0;
    }
    flag = 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T --) sol();
    return 0;
}
/*
1
4 3 10
0 1 2 2
0 1 2
0 1 1 3 4 3 6 3 1 9
*/

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 5916kb

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: 750ms
memory: 22240kb

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 2 1 1 
1 1
0 
0 
8 2
0 1 1 3 3 3 1 1 
0 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 
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: 2ms
memory: 5672kb

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