QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#719686#9459. Tree EquationEstelle_NAC ✓177ms26124kbC++142.7kb2024-11-07 08:02:042024-11-07 08:02:04

Judging History

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

  • [2024-11-07 08:02:04]
  • 评测
  • 测评结果:AC
  • 用时:177ms
  • 内存:26124kb
  • [2024-11-07 08:02:04]
  • 提交

answer

#include <cstdio>
#include <chrono>
#include <vector>
#include <algorithm>
#include <functional>
#include <unordered_map>

#define ull unsigned long long

using namespace std;

const int N = 100005;
const int mask = chrono::steady_clock::now().time_since_epoch().count();

ull shift(ull x)
{
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}

struct Tree
{
    ull f[N];
    int n, Max, dep[N], siz[N];
    
    vector <int> e[N];

    void Hash(int u, ull x)
    {
        f[u] = x;
        for(int v : e[u])
            Hash(v, x), f[u] += shift(f[v]);
    }

    void Input()
    {
        Max = 0;
        for(int i = 1; i <= n; ++ i)
            e[i].clear();
        for(int i = 1, x; i <= n; ++ i)
        {
            scanf("%d", &x);
            if(x)
                e[x].push_back(i);
        }
    }

    void Init(int u, int fa)
    {
        siz[u] = 1;
        dep[u] = dep[fa] + 1;
        Max = max(Max, dep[u]);
        for(int v : e[u])
            Init(v, u), siz[u] += siz[v];
    }

    int cnt = 0;
    void Print(int u, int fa)
    {
        printf("%d ", fa);
        int id = ++ cnt;
        for(int v : e[u])
            Print(v, id);
    }
};
Tree A, B, C;

unordered_map <ull, int> vis[2];
vector < pair <ull, int> > val[2];

void work()
{
    vis[0].clear();
    vis[1].clear();
    val[0].clear();
    val[1].clear();

    scanf("%d%d%d", &A.n, &B.n, &C.n);
    A.Input(), A.Init(1, 0);
    B.Input(), B.Init(1, 0);
    C.Input(), C.Init(1, 0);

    C.Hash(1, 1);
    for(int i = 1; i <= C.n; ++ i)
    {
        if(C.dep[i] == A.Max && !vis[0][C.f[i]])
        {
            vis[0][C.f[i]] = 1;
            A.Hash(1, C.f[i]);
            val[0].push_back({A.f[1], i});
        }
        if(C.dep[i] == B.Max && !vis[1][C.f[i]])
        {
            vis[1][C.f[i]] = 1;
            B.Hash(1, C.f[i]);
            val[1].push_back({C.f[1] + 1 - B.f[1], i});
        }
    }

    sort(val[0].begin(), val[0].end());
    sort(val[1].begin(), val[1].end());

    for(int i = 0, j = 0; i < val[0].size(); ++ i)
    {
        while(j < val[1].size() && val[0][i].first > val[1][j].first)
            ++ j;
        if(j < val[1].size() && val[0][i].first == val[1][j].first)
        {
            int u = val[0][i].second, v = val[1][j].second;
            printf("%d %d\n", C.siz[u], C.siz[v]);
            C.Print(u, C.cnt = 0), printf("\n");
            C.Print(v, C.cnt = 0), printf("\n");
            return;
        }
    }
    printf("Impossible\n");
}

int T;

int main()
{
    scanf("%d", &T);
    while(T --)
        work();

    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 177ms
memory: 26124kb

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: 3ms
memory: 14772kb

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